SPOJ in Gyumri

   Пусть дан ориентированный взвешенный граф с N вершинами и M ребрами. Вершины пронумерованы целыми числами от 1 до N. Требуется найти длину минимального пути от вершины 1 до вершины N. Из всех путей минимальный тот, у которого сумма весов ребер, через которые проходит путь, минимальная.

Входные данные.

   N M

   X[1] Y[1] Z[1]

   X[2] Y[2] Z[2]

   …

   X[M] Y[M] Z[M]

Где:

   N - количество вершин в графе (1 ≤ N ≤ 1000).

   M - количество ребер в графе (1 ≤ M ≤ 1000).

   X[i] Y[i] Z[i] - описание i-ого ребра графа, где X[i] - номер начальной вершины, Y[i] - номер конечной вершины, Z[i] - вес ребра (1 ≤ X[i], Y[i] ≤ N, -1000 ≤ Z[i] ≤ 1000).

   Между двумя вершинами может быть несколько ребер. Ребер из вершины в саму себя нет. В графе нет циклов отрицательного веса.

Выходные данные.

   Ans - длина минимального пути между вершиной 1 и вершиной N.

Пример.