#include <bits/stdc++.h>
using namespace std;
// #define cin fein
// #define cout g
#define NMAX 50100
#define INF 10100000
#define pii pair<int,int>
#define piii pair<int, pii>
ifstream fein("bellmanford.in");
ofstream g("bellmanford.out");
int n, m, dist[NMAX], v[NMAX], iq[NMAX], a, b, c, ok=1;
vector<pii> l[NMAX];
void bellmanFord(int nod)
{
    deque<int> d;
    for(int i=1;i<=n;i++)
    {
        if(i!=nod)
            dist[i]=INF;
    }
    d.push_back(nod);
    while(!d.empty())
    {
        int nc=d.front();
        d.pop_front();
        v[nc]=0;
        for(int i=0;i<l[nc].size();i++)
        {
            int vc=l[nc][i].first;
            int cvc=l[nc][i].second;
            if(dist[vc]>dist[nc]+cvc)
            {
                dist[vc]=dist[nc]+cvc;
                if(!v[vc])
                {
                    d.push_back(vc);
                    v[vc]=1;
                    iq[vc]++;
                    if(iq[vc]>n)
                    {
                        g<<"Ciclu negativ!";
                        ok=0;
                        return;
                    }
                }
            }
        }
    }
}

int main()
{
    fein>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fein>>a>>b>>c;
        l[a].push_back(make_pair(b, c));
    }
    bellmanFord(1);
    if(ok)
    {
        for(int i=2;i<=n;i++)
        {
            g<<dist[i]<<" ";
        }
    }

    return 0;
}