赛车游戏

题目描述

R 君和小伙伴打算一起玩赛车。但他们被老司机 mocania 骗去了秋名山。 秋名山上有 $n$ 个点和 $m$ 条边,R 君和他的小伙伴要从点 $1$ 出发开往点 $n$,每条边都有一个初始的方向。老司机 mocania 拿到了秋名山的地图但却不知道每条路有多长。显然,为了赛车游戏的公平,每条 $1$ 到 $n$ 的路径应当是等长的。mocania 想,我就随便给边表上一个 $1...9$ 的长度,反正傻傻的 R 君也看不出来。 可 mocania 的数学不大好,不知道怎么给边标长度,只能跑来请教你这个 OI 高手了。

输入输出格式

输入格式


第一行两个整数 $n,m$。 接下来 $m$ 行,每行两个整数 $u,v$,表示一条从 $u$ 到 $v$ 的有向边。

输出格式


如果无解或者不存在 $1$ 到 $n$ 的路径直接输出一个 -1。 如果有解第一行输出两个数 $n,m$,和输入文件中给出的相同。 借下来 $m$ 行,每行三个整数 $u,v,w$,表示把从 $u$ 到 $v$ 的路径的长度设置为 $w$,其中 $w$ 是一个 $1...9$ 的整数。要求所有边的出现顺序和题目中给出的相同。

输入输出样例

输入样例 #1

10 10
1 2
2 3
3 4
4 5
5 6
6 7
7 8
8 9
9 10
1 10

输出样例 #1

10 10
1 2 1
2 3 1
3 4 1
4 5 1
5 6 1
6 7 1
7 8 1
8 9 1
9 10 1
1 10 9

说明

#### 数据范围 **本题启用 Special Judge 和 Subtask。** Subtask #1:$30\%$ 的分数,$n \leq 10,\ m \leq 20$; Subtask #2:$60\%$ 的分数,$n \leq 100,\ m \leq 200$; Subtask #3:$100\%$ 的分数,$n \leq 1000\ m \leq 2000$。 保证数据中不会出现重边,自环。