P5590 赛车游戏

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

#### 数据范围 **本题启用 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$。 保证数据中不会出现重边，自环。