#include<fstream>
#include<vector>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const unsigned short N=50001;
vector<pair<unsigned short,int>> g[N];
unsigned short d[N],h[N],p[N];
int main()
{
    unsigned short k=1,n;
    int m;
    for(cin>>n>>m;m--;) {
        unsigned short i,j,k;
        cin>>i>>j>>k,g[i].push_back({j,k});
    }
    for(int i=2;i<=n;d[i]=p[i]=N,++i);
    for(p[1]=h[1]=1;k;) {
        int i=h[1],w=1;
        for(h[1]=h[k--],p[h[1]]=1;w<<1<=k;) {
            int f=w<<1;
            if(f<k&&d[h[f+1]]<d[h[f]])
                ++f;
            if(d[h[w]]<=d[h[f]])
                break;
            swap(h[w],h[f]),p[h[w]]=w,p[h[f]]=f,w=f;
        }
        for(auto j:g[i])
            if(d[j.first]>d[i]+j.second) {
                if(d[j.first]=d[i]+j.second,p[j.first]==N)
                    h[++k]=j.first,p[h[k]]=k;
                for(int w=p[j.first];w>1&&d[h[w>>1]]>d[h[w]];) {
                    int f=w>>1;
                    swap(h[w],h[f]),p[h[w]]=w,p[h[f]]=f,w=f;
                }
            }
    }
    for(int i=2;i<=n;cout<<(d[i]==N?0:d[i])<<' ',++i);
    return 0;
}