#include <bits/stdc++.h>
#define mp make_pair
using namespace std;
ifstream f("bellmanford.in");
ofstream g("bellmanford.out");
const long long nmax = 50005;
const long long inf = 100000005;
long long n, m, cost[nmax];
vector< pair< long long, pair<long long, long long> > > E;
void bellman(long long nod)
{
sort(E.begin(), E.end());
for(long long i = 1; i <= n; i ++)
cost[i] = inf;
long long ok = 1; cost[nod] = 0;
for(long long i = 1; i < n && ok; i ++)
{
ok = 0;
for(long long j = 0; j < m; j ++)
{
long long x = E[j].first;
long long y = E[j].second.first;
long long c = E[j].second.second;
if(cost[y] > cost[x] + c)
cost[y] = cost[x] + c, ok = 1;
}
for(long long j = 0; j < m; j ++)
{
long long x = E[j].first;
long long y = E[j].second.first;
long long c = E[j].second.second;
if(cost[y] > cost[x] + c)
{
g << "Ciclu negativ!";
exit(0);
}
}
}
}
int main()
{
f >> n >> m;
for(long long i = 1; i <= m; i ++)
{
long long x, y, c;
f >> x >> y >> c;
E.push_back(mp(x, mp(y, c)));
}
bellman(1);
for(long long i = 2; i <= n; i ++)
g << cost[i] << " ";
return 0;
}