#include <fstream>
#include <list>
#define DIM 50011
#define INF 1530011
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n,m,D[DIM],H[DIM],dH;
bool viz[DIM];

list<pair<int,int> > L[DIM];
list<pair<int,int> >::iterator it;

void stergere(){
    int c,p,aux;
    H[1]=H[dH],dH--;
    p=1,c=2;
    while(c<=dH){
        if(c+1<=dH && D[H[c]]>=D[H[c+1]])
            c++;
        if(D[H[p]]>=D[H[c]])
            aux=H[p],H[p]=H[c],H[c]=aux;
        p=c,c*=2;
    }
}

void update(int x){
    int p,c,aux;
    H[++dH]=x;
    c=dH,p=c/2;
    while(p>0){
        if(D[H[p]]>D[H[c]])
            aux=H[p],H[p]=H[c],H[c]=aux;
        c=p,p/=2;
    }
}

int main(void){
    register int i,j,x,y,c,p;
    pair<int,int> q;

    f>>n>>m;
    for(i=1;i<=n;i++)
        f>>x>>y>>c,L[x].push_back(make_pair(y,c));
    for(i=2;i<=n;i++)
        D[i]=INF;

    H[1]=1,dH=1;
    while(dH){
        p=H[1];
        stergere();
        if(viz[p])
            continue;
        for(it=L[p].begin();it!=L[p].end();it++){
            q=*it;
            if(!viz[q.first] && D[p]+q.second<=D[q.first]){
                D[q.first]=D[p]+q.second;
                update(q.first);
            }
        }
        viz[p]=true;
    }

    for(i=2;i<=n;i++){
        if(D[i]==INF) g<<"0 ";
        else g<<D[i]<<" ";
    }
    f.close();
    g.close();
    return 0;
}