#include <fstream>
#include <cstring>
#include <vector>
#include <set>
#define DIM 50100

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int N,M,n;
vector < pair<int,int> > v[DIM],H(DIM);
void upheap(int x){
    int c=x;
    int p=c/2;
    while(p>=1 && H[p].second>H[c].second){
        swap(H[c],H[p]);
        c=p;
        p/=2;
    }
}
void downheap(int x){
    int p=x;
    int c=p*2;
    while(c<=n){
        if(c+1<=n && H[c].second>H[c+1].second);
            c++;
        if(H[p].second>H[c].second){
            swap(H[c],H[p]);
            p=c;
            c*=2;
        }
        else
            break;
    }
}
void insert(int x,int y){
    H[++n]=make_pair(x,y);
    upheap(n);
}
void delete_root(){
    swap(H[n],H[1]);
    n--;
    downheap(1);
}
int D[DIM];
int main(){
    fin>>N>>M;
    while(M--){
        int x,y,cost;
        fin>>x>>y>>cost;
        v[x].push_back(make_pair(y,cost));
    }
    memset(D,0x3f3f3f3f,sizeof(D));
    D[1]=0;
    insert(1,0);
    while(n!=0){
        int nod=H[1].first;
        int val=H[1].second;
        delete_root();
        for(std::vector <pair <int,int> >::iterator it=v[nod].begin();it!=v[nod].end();it++)
            if(D[it->first]>val+it->second){
                D[it->first]=val+it->second;
                insert(it->first,D[it->first]);
            }
    }
    for(int i=2;i<=N;i++)
        if(D[i]==0x3f3f3f3f)
            fout<<"0 ";
        else
            fout<<D[i]<<" ";
    fin.close();fout.close();
    return 0;
}