Description

    Mar 星球上共有 n 个城市（编号为 1∼n），城市之间为了方便交通修建了 m 条单向高速公路。

    有些公路是为了交通方便连接了 2 个不同的城市，有些公路是为了观光方便，从一个城市出发最后还会回到该城市。两个城市之间、以及从本市出发回本市的道路都可能有多条。

    作为交通部新来的程序员，你接到了一个第一个任务：已知所有道路起止点以及走该条路需要花的过路费，计算出从 1 号城市到 n 号城市的最低花费？

Input Format

第 1 行有 2 个整数 n 和 m（1≤n,m≤105）

接下来 m 行，每行有 3 个整数 u、v、p，表示从有一条道路从 u 市连到 v 市，走该条路需要花费 p 元。（1≤u,v≤n，1≤p≤104）。

Output Format

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

2

Source