题目描述

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\sim 9$ 的整数。要求所有边的出现顺序和题目中给出的相同。

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

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（$30$ 分）：$n \leq 100$，$m \leq 200$；
Subtask #3（$40$ 分）：$n \leq 1000$，$m \leq 2000$。

保证数据中不会出现重边，自环。