The sweltering summer has arrived, but Chotu still has classes to
attend. The map of Chotu's college is given in the form of a graph with vertices representing junctions and edges representing the roads. There is at most one road between two junctions and there is no road from a junction to itself. The length of each road is given.

Chotu has to go from his hostel (node numbered as 1) to CC-3 (node numbered as N). Now, as it is very hot outside, Chotu will only travel on any of the shortest paths from node 1 to node N. Chotu sees the map and observes that there are many roads that he will never take, i.e., there are some roads that do not occur on any of the shortest paths from his hostel to CC-3. He wants to remove these roads from the graph. Your task is to calculate the sum of all the distances of the roads that are present in
the final graph. If it is impossible to reach CC-3 from his hostel, then print -1.
INPUT
First line of input contains 2 integers N and M, which are the number of vertices and number of edges in the graph.
Then follow M lines, each containing 3 integers, u, v, w, denoting an undirected edge from u to v with length w.
OUTPUT
Output a single line containing the required answer.

Constraints

N is the number of junctions while M is the number of roads.
Hostel is always at junction 1 and CC-3 is at junction N

2 ≤ N ≤ 100000
1 ≤ M ≤ min(500000, N * (N-1) / 2)

SAMPLE INPUT
3 3
1 2 3
2 3 2
1 3 4

SAMPLE OUTPUT
4

见题面

见题面