#include<fstream>
#include<vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
vector<pair<unsigned short,int>> a[50001];
int d[50001],h[50001],t;
void A(int k)
{
    int l=d[h[k]],u=h[k];
    for(;k>1&&l<d[h[k>>1]];h[k]=h[k>>1],k>>=1);
    h[k]=u;
}
void B(int k)
{
    int i;
    do {
        i=0;
        if(2*k<=t) {
            if(i=2*k,2*k<t&&d[h[2*k+1]]<d[h[2*k]])
                i=2*k+1;
            if(d[h[i]]>=d[h[k]])
                i=0;
        }
        if(i)
            swap(h[k],h[i]),k=i;
    } while(i);
}
int main()
{
    unsigned short n;
    int m;
    for(cin>>n>>m;m--;) {
        int i,j,k;
        cin>>i>>j>>k,a[i].push_back({j,k});
    }
    for(int i=2;i<=n;++i)
        d[i]=2e9,h[++t]=i,A(t);
    for(d[1]=0,h[++t]=1,A(t);t;) {
        int i=h[1];
        h[1]=h[t--],B(h[1]);
        for(auto j:a[i])
            if(d[j.first]>d[i]+j.second)
                d[j.first]=d[i]+j.second,A(h[j.first]);
    }
    for(int i=2;i<=n;cout<<(d[i]==2e9?0:d[i])<<' ',++i);
    return 0;
}