#include<bits/stdc++.h>

#define inf 0x3f3f3f3f
#define pb push_back
#define mp make_pair
#define nod first
#define cost second

using namespace std;

ifstream f("bellmanford.in");
ofstream g("bellmanford.out");

const int NMAX = 50001;
vector< pair<int, int> > G[NMAX];
vector< pair<int, int> >::iterator Vecin;
queue<int>Q;
int n, m, x, y, c, Nod;

int main()
{
    int D[NMAX],ItNod[NMAX];
    bool USED[NMAX];
    f>>n>>m;

    for(int i = 1; i <= m; i++)
    {
        f>>x>>y>>c;
        G[x].pb(mp(y, c));
    }

    memset(D, inf, sizeof(D));
    memset(USED, false, sizeof(USED));
    memset(ItNod, 0, sizeof(ItNod));

    int Start_Point = 1;
    D[Start_Point] = 0;
    USED[Start_Point] = true;
    Q.push(Start_Point);
    ItNod[Start_Point] ++;

    while(!Q.empty())
    {
        Nod = Q.front();
        Q.pop();
        USED[Nod] = false;
        for(int i = 0; i < G[Nod].size(); i++)
        {
            if(D[(G[Nod][i]).nod] > D[Nod] + (G[Nod][i]).cost)
            {
                D[(G[Nod][i]).nod] = D[Nod] + (G[Nod][i]).cost;
                if(!USED[(G[Nod][i]).nod])
                {
                    USED[(G[Nod][i]).nod] = true;
                    Q.push((G[Nod][i]).nod);
                    ItNod[(G[Nod][i]).nod] ++;
                    if(ItNod[(G[Nod][i]).nod] > n)
                    {
                        g<<"Ciclu negativ!"<<"\n";
                        return 0;
                    }
                }
            }
        }
    }

    for(int i = 2; i <= n; i++)
        g<<D[i]<<" ";

    return 0;
}