题目描述

输入一个有向图，边的权值可正可负，求顶点到其他各点的最短路。

输入格式

第一行输入n，m。表示n个结点（默认顶点为1号），m条边。（n，m≤100）

接下来m行，每行三个整数，空格分隔，表示起点、终点、边权。（边权绝对值≤10000）

输出格式

输出一行，如果有负权回路输出“not possible”，否则输出顶点1到除自己外其他点的最短路，输出答案之间仅有一个空格。

5 5
2 3 2
1 2 -3
1 5 5
4 5 2
3 4 3

-3 -1 2 4