#include <cstdio>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f

using namespace std;

FILE *f=fopen("bellmanford.in","r"),*g=fopen("bellmanford.out","w");
int n,m,dist[50001],pred[50001],schimbari=true,v,a,b,c,nr_in_queue[50001];
bool in_queue[50001],ciclu_negativ;
vector <pair <int,int> > u[50001];
queue <int> Q;

void citire()
{
    fscanf(f,"%i %i",&n,&m);
    for(int i=1;i<=m;i++)
    {
        fscanf(f,"%i %i %i",&a,&b,&c);
        u[a].push_back(make_pair(b,c));
    }
}

void bellmanfordfast()
{
    int x;
    for(int i=1;i<=n;i++)
        dist[i]=inf;
    dist[1]=0;
    Q.push(1);
    while(!Q.empty() && !ciclu_negativ)
    {
        x=Q.front();
        Q.pop();
        in_queue[x]=false;
        for(int i=0;i<u[x].size();i++)
            if(dist[x]+u[x][i].second<dist[u[x][i].first])
            {
                dist[u[x][i].first]=dist[x]+u[x][i].second;
                if(!in_queue[u[x][i].first])
                {
                    if(nr_in_queue[u[x][i].first]>n)
                    {
                        ciclu_negativ=true;
                        break;
                    }
                    else
                    {
                        Q.push(u[x][i].first);
                        in_queue[u[x][i].first]=true;
                        nr_in_queue[u[x][i].first]++;
                    }
                }

            }

    }
}

int main()
{
    citire();
    bellmanfordfast();
    if(ciclu_negativ)
    {
        fprintf(g,"Ciclu negativ!");
        return 0;
    }
    for(int i=2;i<=n;i++)
        fprintf(g,"%i ",dist[i]);
    return 0;
}