题目描述

Beerland 有 $N$ 个城市和 $M$ 条双向道路，城市编号为 $1\sim N$，首都为城市 $1$。每条道路有一个正整数长度。

给定道路集合中的一个特殊子集 $T$。$T$ 恰好构成一棵以 $1$ 为根的树，并满足：对每个城市 $v$，只使用 $T$ 中道路时，从首都到 $v$ 的唯一树上路径也是原图中的一条最短路。因此 $T$ 是一棵最短路树。

总统平时只沿 $T$ 中道路出行。现在对每个城市 $i\;(2\le i\le N)$，假设从首都到 $i$ 的树上路径中的最后一条道路（即 $i$ 与其父亲之间的树边）被破坏，不能再使用。求此时从城市 $1$ 到城市 $i$ 的最短路长度；如果无法到达，输出 -1。

每个城市的询问互相独立，即每次只删除该城市对应的那一条树边。

输入格式

第一行两个整数 $N,M$，其中 $N\le4000$，$M\le100000$。

接下来 $M$ 行，每行四个整数 $a_j,b_j,l_j,t_j$：

• $a_j,b_j$：道路两端城市，$1\le a_j,b_j\le N$ 且 $a_j\ne b_j$；
• $1\le l_j\le10^5$：道路长度；
• $t_j=1$ 表示该道路属于最短路树 $T$，否则 $t_j=0$。

保证所有 $t_j=1$ 的道路满足题目所述最短路树性质。两个城市之间允许存在多条道路。

输出格式

输出 $N-1$ 个整数。第 $i$ 个数表示删除城市 $i+1$ 的父边后，从城市 $1$ 到城市 $i+1$ 的最短路长度；不可达则输出 -1。

样例

5 9
3 1 3 1
1 4 2 1
2 1 6 0
2 3 4 0
5 2 3 0
3 2 2 1
5 3 1 1
3 5 2 0
4 5 4 0

6 7 8 5