#include<fstream>
#include<vector>
#define lmare 132000
#define lmic 51000
#define infinit 300000
using namespace std;
 
struct muchie{
    int inf;
    int cost;
}y;
vector<muchie>v[lmic];
int D[lmic];
int parcurs[lmic];
int h[lmare];
 
void creareheap(int nod, int st, int dr){
    if(st==dr){
        if(st==1)h[nod]=0;
        else h[nod]=infinit;
        D[st]=infinit;
    }
    else{
        int mij=(st+dr)/2;
        creareheap(2*nod,st,mij);
        creareheap(2*nod+1,mij+1,dr);
        if(h[2*nod]<h[2*nod+1])h[nod]=h[2*nod];
        else h[nod]=h[2*nod+1];
    }
}
 
void actualizareheap(int nod,int st,int dr,int cost,int p){
    if(st==dr)h[nod]=cost;
    else{
        int mij=(st+dr)/2;
        if(p<=mij)actualizareheap(2*nod,st,mij,cost,p);
        else actualizareheap(2*nod+1,mij+1,dr,cost,p);
        if(h[2*nod]<h[2*nod+1])h[nod]=h[2*nod];
        else h[nod]=h[2*nod+1];
   }
}
 
void parcurg(int a,int n){
    int i;
    for(i=0;i<v[a].size();i++)
        if((parcurs[v[a][i].inf]==0)&&(D[a]+v[a][i].cost<D[v[a][i].inf])){
            D[v[a][i].inf]=D[a]+v[a][i].cost;
            actualizareheap(1,1,n,D[v[a][i].inf],v[a][i].inf);}
    parcurs[a]=1;
}
 
int minim(int nod,int st,int dr){
    if(st==dr)return st;
    else{
        int mij=(st+dr)/2;
        if(h[2*nod]<h[2*nod+1])return minim(2*nod,st,mij);
        return minim(2*nod+1,mij+1,dr);
    }
}
 
void afisare(int n){
    int i;
    ofstream g("dijkstra.out");
    for(i=2;i<=n;i++)
        if(D[i]!=infinit)g<<D[i]<<" ";
    else g<<"0"<<" ";
}
main(){
    int n,m,a,i;
    ifstream f("dijkstra.in");
    f>>n>>m;
    for(i=1;i<=m;i++){
        f>>a>>y.inf>>y.cost;
        v[a].push_back(y);}
    creareheap(1,1,n);
    while(h[1]!=infinit){
        a=minim(1,1,n);
        D[a]=h[1];
        parcurg(a,n);
        actualizareheap(1,1,n,infinit,a);
    }
    afisare(n);
}