#include<stdio.h>
#include<vector>
#include<queue>
#define INF 2000000000
using namespace std;
struct Graf{
  int node,cost;
};
vector <Graf> v[50010];
queue<int> heap;
int dist[50010],vc[50010],nr[50010];
int main (){
    FILE *in, *out;
    in = fopen ("bellmanford.in","r");
    out = fopen ("bellmanford.out","w");
    int n,m,i,a,b,c,nod,nods,pp;

    fscanf(in,"%d%d",&n,&m);
    for(i=1;i<=m;i++){
        fscanf(in,"%d%d%d",&a,&b,&c);
        v[a].push_back({b,c});
    }
    pp = 0;
    nods = 1;
    heap.push(nods);
    for(i=1;i<=n;i++)
        dist[i] = INF;
    dist[nods] = 0;
    while(heap.empty() == 0 && pp == 0){// pp - am gasit ciclu
        nod = heap.front();
        heap.pop();
        vc[nod] = 0;
        if(dist[nod] < INF)
            for(i = 0; i < v[nod].size(); i ++)
                if(dist[v[nod][i].node] > dist[nod] + v[nod][i].cost){
                    dist[v[nod][i].node] = dist[nod]+ v[nod][i].cost;
                    if(vc [v[nod][i].node] == 0){
                        if(nr[v[nod][i].node] > n){
                            fprintf(out,"Ciclu negativ!");
                            pp = 1;
                        }
                        heap.push(v[nod][i].node);
                        vc[v[nod][i].node] = 1;
                        nr[v[nod][i].node]++;
                    }
                }
    }
    if (pp == 0)
      for(i=2;i<=n;i++)
          fprintf(out,"%d ",dist[i]);

    fclose (in);
    fclose (out);
    return 0;
}