#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <limits.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
queue <int> Q;
vector < pair <int, int> > L[50001];
int D[50001], Count[50001];
int n , m;
void Citire()
{ int i , x, y, c;
    f>>n>>m;
    for(i=1;i<=m;i++)
    { f>>x>>y>>c;
        L[x].push_back(make_pair(y,c));
    }
}
void Bellman_Ford()
{ int i,j,ok=0,k,l;
       for(i=1;i<=n;i++)
        D[i]=INT_MAX;
D[1]=0; Q.push(1);
    while(!Q.empty()&&(ok!=1))
    { j=Q.front();
        Q.pop();
        for(k=0;k<L[j].size();k++)
        { l=L[j][k].second;
          int nr=L[j][k].first;
        if(D[j]!=INT_MAX&&D[nr]>D[j]+l)
         {  if(Count[nr]>n)
            ok=1;
            else { D[nr]=D[j]+l;
                Q.push(nr);
                Count[nr]++;
                 }
         }
        }
    }
 for(i=2;i<=n;i++)
 if(D[i]!=INT_MAX)
   g<<D[i]<<" ";
   else g<<0;
}
int main()
{
    Citire();
Bellman_Ford();

    return 0;
}