#include <fstream>
#include <vector>
#include<limits.h>
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
vector <pair<int,int> >a[50001];
unsigned int i,m,n,x,y,z,p,u,q[500001],nre[50001],c[50001];
bool viz[50001];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>x>>y>>z;
        a[x].push_back(make_pair(y,z));
        nre[x]++;
    }
    q[1]=p=u=1;
    for(i=2;i<=n;i++)
        c[i]=INT_MAX;
    while(p<=u){
        viz[q[p]]=1;
        for(i=0;i<nre[q[p]];i++){
            if(c[a[q[p]][i].first]>c[q[p]]+a[q[p]][i].second){
                c[a[q[p]][i].first]=c[q[p]]+a[q[p]][i].second;
                q[++u]=a[q[p]][i].first;
            }

        }
        viz[q[p++]]=0;
    }
    for(i=2;i<=n;i++)
        if(c[i]==INT_MAX)
            g<<0<<' ';
        else g<<c[i]<<" ";
    return 0;
}