#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
fstream in("dijkstra.in",ios::in),out("dijkstra.out",ios::out);

const int M=1+25e4;
const int N=1+5e4;
#define INF 0x3f3f3f3f
int h[N],nh,n,m,d[N],poz[N];
bool inh[N];
struct Edge{
    int d,c;
    Edge(int a, int b){d=a;c=b;}
};
vector<Edge> g[N];

void schimba(int a,int b){
    int c=h[a];
    h[a]=h[b];
    h[b]=c;
    poz[h[a]]=a;
    poz[h[b]]=b;
}
void up(int p){
    while(p>1 && d[h[p]]<d[h[p/2]]){
        schimba(p,p/2);
        p/=2;
    }
}
void down(int p){
    int fs=2*p,fd=2*p+1,bun=p;
    if(fs<=nh && d[h[fs]]<d[h[bun]])
        bun=fs;
    if(fd<=nh && d[h[fd]]<d[h[bun]])
        bun=fd;
    if(bun!=p){
        schimba(p,bun);
        down(bun);
    }
}
void push(int x){
    h[++nh]=x;
    inh[x]=true;
    poz[x]=nh;
    up(nh);
}
void pop(){
    schimba(1,nh--);
    down(1);
}
int a,b,c;
int cost(int a, int b){

}
void dijkstra(int s){
    for(int i=1 ; i<=n ; i++){
        d[i]=INF;
    }
    d[s]=0;
    push(s);
    poz[s]=1;
    while(nh){
        int x=h[1];
        pop();
        for(int i=0 ; i<g[x].size() ; i++){
            int y=g[x][i].d, v=d[x]+g[x][i].c;
            if(v<d[y]){
                d[y]=v;
                if(!inh[y])
                    push(y);

            }
        }
    }
}
int main()
{
    in>>n>>m;
    while(in>>a>>b>>c){
        g[a].push_back(Edge(b,c));
    }
    dijkstra(1);
    for(int i=2 ; i<=n ; i++){
        if(d[i]==INF) out<<"0 ";
        else out<<d[i]<<' ';
    }
    return 0;
}