【题目背景】

道情非是等閒情，旣識天機不可輕。

先把世情齊放下，次將道理細研精。

未煉還丹先煉性，未修大藥且修心。

心修自然丹信至，性淸自然藥材生。

藥材生，緊加功。雷聲隱隱震虛空。

電光灼處尋眞種，風信來時覓本宗。

霞光萬道籠金鼎，紫雲千丈罩天門。

若還到此休驚怕，穩把元. 神守洞門。
.
如猫捕鼠兎逢鷹，急急着力又加勤。

萬般景象皆非類，一顆紅光是至眞。

此箇紅光是春意，其中有若明窗塵。

中懸一點先天藥，遠似葡萄近似金。

到此全憑要謹愼，絲毫念起喪天眞。

待他一點自歸伏，身中化作四時春。

一片白雲香一陣，一番雨過一番新。

終日綿綿如醉漢，悠悠只等洞中春。

遍體陰精都剝盡，化作純陽一塊金。

此時氣絕如小死，打成一片是全眞。
到此功成纔了當，卻來塵世積功勛。

行滿功成天命詔，陽神出現了眞靈。

此言休向非人說，不逢達者莫輕論。

其中切切通玄理，此眞之外更無眞。

收拾行囊牢封固，他日成功可印心。

可印心，五十二句要君尋。

若有虛言遭天譴，說與非人鞭喪身。

——张三丰《道情歌》

【题目描述】

给定一张 $n$ 个点 $m$ 条边的无向图（可能存在重边）。

已知第 $i$ 条边的权值 $w_i \in [l_i, r_i]$，且 $\{w_m\}$ 是 $1$ ∼ $m$ 的排列。

在前 $n − 1$ 条边构成最小生成树的前提下，最小化 $\{w_m\}$ 的字典序。

【输入格式】

第一行两个整数 $n$, $m$。

接下来 $m$ 行，第 $i$ 行四个整数 $u_i$, $v_i$, $l_i$, $r_i$，表示第 $i$ 条边为 $(u_i, v_i)$。

【输出格式】

如果不存在合法的 $\{w_m\}$，输出一行一个整数 $−1$。

否则，输出一行 $m$ 个整数 $w_1, w_2,... , w_m$。

【样例1输入】

4 5
1 3 1 3
1 4 2 4
1 2 1 4
2 3 3 3
2 3 3 5

【样例1输出】

1 4 2 3 5

【样例2输入】

3 3
1 2 2 3
2 3 2 3
1 3 1 3

【样例2输出】

-1

【数据范围】

保证 $1 ≤ n − 1 ≤ m ≤ 3500, 1 ≤ ui < vi ≤ n, 1 ≤ li ≤ ri ≤ m$。

保证给出的前 $n − 1$ 条边构成原图的一棵生成树。