1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;
#define INF 987654321
int	n, m, i, d[502], a1, a2, a3;
pair<pair<int, int>, int> a[6002];
int main() {
	cin >> n >> m;
	for (i = 0; i < m; i++)
		cin >> a[i].first.first >> a[i].first.second >> a[i].second;
	fill(d, d + n + 1, INF);
	d[1] = 0;
	for (i = 1; i <= n; i++)
		for (auto t : a)
			if (d[t.first.first] != INF && d[t.first.second] > d[t.first.first] + t.second) {
				d[t.first.second] = d[t.first.first] + t.second;
				if (i == n) {
					cout << -1 << endl;
					return 0;
				}
			}
	for (i = 2; i <= n; i++)
		if (d[i] == INF)	cout << -1 << endl;
		else	cout << d[i] << endl;
}