#include <cstdio>
#include <queue>
#include <vector>
#include <utility>
using namespace std;
int i,j,m,n,x,y,c,acc[50009],d[50008],k;
bool ok[50090],ok1;
vector <pair<int,int> > v[50005];
vector <pair<int,int> >::iterator it;
queue <int> q;
int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d %d",&n,&m);
    for(i=1; i<=m ;i++)
    {
        scanf("%d %d %d",&x,&y,&c);
        v[x].push_back(make_pair(y,c));
    }
    q.push(1);ok[1]=true;
    for(i=2; i<=n; i++)
    d[i]=9999999;
    while(!q.empty())
    {
        k=q.front();
        q.pop();
        ok[k]=false;
        for(it=v[k].begin(); it!=v[k].end(); it++)
        {
            if(d[(*it).first]> d[k]+(*it).second )
            {
                d[(*it).first]=d[k]+(*it).second;
                if(!ok[(*it).first])
                {
                  ok[(*it).first]=true;
                  q.push((*it).first);
                  if(++acc[(*it).first]>n) {printf("Ciclu negativ!");return 0;}

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

    return 0;
}