输入描述:

第一行三个正整数，分别为点数N，边数M，源点S；

以下M行，每行三个整数a,b,c，表示点a,b之间连有一条边，权值为c。

输出描述:

如果存在负权环，只输出一行-1，否则按以下格式输出：
共N行，第i行描述S点到点i的最短路：

如果S与i不连通，输出NoPath；

如果i=S，输出0。

其他情况输出S到i的最短路的长度。

备注:

对于全部数据，。