#include<stdio.h>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std ;

#define dim 50500
#define pb push_back
#define mp make_pair
#define fs first
#define sc second
vector <pair < int ,int> > v[dim];
queue <int> q;
int a[dim],n,m,x,y,c,dst[dim];
void read()
{
    scanf("%d%d",&n,&m);
    for(int i=1 ;i<=m;i++)
    {
        scanf("%d%d%d",&x,&y,&c);
        v[x].pb(mp(y,c));
     //  printf("%d %d %d \n",x,y,c);
    }
}
void init ()
{
     for(int i=0;i<=n+1;i++)
     dst[i] = 500100;
}
void solve()
{
     init ();
        int x,i,y,c;
        dst[1] = 0;
        for(q.push(1) ; !q.empty() ; q.pop() )
        {
            x = q.front();
            if ( a[1]!=0 && x==1 ) 
            continue;
            for(i=0 ; i<v[x].size()  ; i++)
            {
                y=v[x][i].fs;
                c=v[x][i].sc;
                if ( dst[x]+c <dst[y] ) 
                {
                    dst[y] = dst[x] +c;
                    q.push( y );
                    a[y]++;
                    if ( a[y]==n-1 )
                    printf("Ciclu negativ!");
                }
            }
        }
    for(int i=2 ;i<=n;i++)
    printf("%d ",dst[i]);
}
int main ()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    read();
    solve();
    return 0;

}