# include <bits/stdc++.h>
# define x first
# define y second
# define mp make_pair
using namespace std;
ifstream fi("bellmanford.in");
ofstream fo("bellmanford.out");
int d[50005];
vector < pair < int , int > > s[50005];
int nr[500005];
bitset < 50005 > bv;
int main(void)
{
    int n,m;
    fi>>n>>m;
    int a,b,c;
    for (int i = 1;i <= m;++i)
        fi>>a>>b>>c,s[a].push_back(mp(b,c));
    for (int i = 2;i <= n;++i) d[i] = 2e9;
    queue < int > q;
    q.push(1);
    while (!q.empty())
    {
        int v = q.front();q.pop();
        bv[v] = 0;
        for (vector < pair < int , int > > :: iterator it = s[v].begin();it != s[v].end();++it)
            if (d[it->x] > d[v] + it->y)
                {
                    d[it->x] = d[v] + it->y;
                    if (!bv[it->x])
                    {
                        if (nr[it->x] > n)
                            return fo << "Ciclu negativ!\n",0;
                        d[it->x] = d[v] + it->y;
                        nr[it->x]++;
                        bv[it->x] = 1;
                        q.push(it->x);
                    }
                }
    }
    for (int i = 2;i <= n;++i) fo << d[i] << ' ';
    fo << '\n';
    return 0;
}