#include <cstdio>
#include <queue>
#include <vector>

using namespace std;

int N,M;
bool in[50001];
int nrq[50001];

vector < pair<int,int> > g[50001];
queue <int> Q;
int best[50001];

int main()
{
    freopen ("bellmanford.in","r",stdin);
    freopen ("bellmanford.out","w",stdout);

    scanf ("%d %d",&N,&M);
    int i,x,y,c;

    for (i=1; i<=M; i++)
    {
        scanf ("%d %d %d",&x,&y,&c);
        g[x].push_back(make_pair(y,c));
    }

    for (i=2; i<=N; i++)
    {
        best[i]=2000000000;
    }

    int S=1;
    Q.push(S);
    in[S]=true;
    best[S]=0;
    nrq[S]++;

    int j,node;
    while (!Q.empty())
    {
        node=Q.front();
        Q.pop();
        in[node]=false;
        for (j=0; j<g[node].size(); j++)
        {
            if (best[g[node][j].first]>best[node]+g[node][j].second)
            {
                best[g[node][j].first]=best[node]+g[node][j].second;
                if (in[g[node][j].first]==false)
                {
                    Q.push(g[node][j].first);
                    in[g[node][j].first]=true;
                    nrq[g[node][j].first]++;

                    if (nrq[g[node][j].first]>N)
                    {
                        printf ("Ciclu negativ!\n");
                        return 0;
                    }
                }
            }
        }
    }

    for (i=2; i<=N; i++)
    {
        printf ("%d ",best[i]);
    }
    printf ("\n");

    return 0;
}