题目背景

题目描述

机房爆发了可怕的发烧病毒，你要尽快的逃离。

给定一张 $n$ 个的点 $m$ 条边的无向连通图，边有边权。

你所在的地方位于 $1$ 号节点，你要尽快的跑到 $n$ 号节点。

但是还有有 $n+m$ 个限制，你要分别满足每个限制，求出一条从 $1$ 到 $n$ 的最短路：

前 $n$ 个限制中，第 $i$ 个限制要求必须经过 $i$ 号节点；

后 $m$ 个限制中，第 $i$ 个限制要求必须经过第 $i$ 条边。

输入格式

第一行三个整数，$n,m,type$，$type\in \{0,1\}$，含义见输出格式。

接下来 $m$ 行每行三个整数，分别表示第 $i$ 条边的起点、终点和边权。

输出格式

如果 $type = 0$，输出 $n$ 行，每行一个整数，第 $i$ 行表示满足第 $i$ 个限制下的 $1$ 到 $n$ 的最短路的大小。

如果 $type = 1$，输出 $n+m$ 行，每行一个整数，第 $i$ 行表示满足第 $i$ 个限制下的 $1$ 到 $n$ 的最短路的大小。

样例1

样例输入1

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

样例输出1

10
12
10
10
12
12
10
10

样例2

样例输入2

6 8 1
1 3 3
1 5 2
1 6 4
2 5 1
2 6 6
3 4 3
3 5 2
4 5 4

样例输出2

4
9
10
16
8
4
10
8
4
9
9
16
11
16

样例3

见下发文件。

数据范围

对于所有的数据，保证 $n \leq 1\times 10^5, m \leq 2\times 10^5$，$1 \leq u_i,v_i \leq n$，$1 \leq w_i \leq 1\times 10^4$。

每个测试点的具体限制见下表：

时间限制：$\texttt{1s}$

空间限制：$\texttt{512MB}$