#include<stdio.h>
#include<vector>
#include<utility>
#include<list>
#include<queue>
using namespace std;
#define inf 2000000
typedef pair <int, int> per;
int n,m,x,y,v;
vector<list<per> >graf;
list<per>::iterator it, last;
vector <bool> inCoada;
vector <int> aparitii, dist;
per aux;

int bellman()
{
    int top, nod, cost;
    queue<int> coada;
    ++aparitii[1];
    dist[1] = 0;
    coada.push(1);
    while(!coada.empty())
    {
        top=coada.front();
        inCoada[top] = 0;
        coada.pop();
        last=graf[top].end();
        for(it=graf[top].begin();it!=last;it++)
        {
            nod=it->first; cost=it->second;
            if(dist[nod]>dist[top]+cost)
            {
                dist[nod]=dist[top]+cost;
                if(!inCoada[nod])
                    inCoada[nod] = true, coada.push(nod);
                ++aparitii[nod];
                if(aparitii[nod] >= n) return 0;
            }
        }
    }
    for(int i = 2; i <= n; ++i)
    printf("%d ",dist[i]);
    return 1;
}

int main()
{
    freopen("bellmanford.in","r",stdin);
    freopen("bellmanford.out","w",stdout);
    scanf("%d%d",&n,&m);
    graf.resize(n+1);
    inCoada.resize(n+1);
    aparitii.resize(n+1);
    dist.resize(n+1, inf);
     for(int i = 1; i <= m; ++i){
    scanf("%d %d %d",&x,&aux.first,&aux.second);
    graf[x].push_back(aux);
}
    if(!bellman()) printf("Ciclu negativ!");
}