#include <iostream>
#include <fstream>
#include <vector>
#define NMAX 50005
#define INF 1e9
using namespace std;

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

struct graph {
    int n,c;
};
vector <graph> g[NMAX];
int n,m;
int h[NMAX],v[NMAX],pos[NMAX];

void change(int p,int q) {
    swap(h[q],h[p]);
    pos[h[p]]=p;
    pos[h[q]]=q;
}
void up(int k) {
    while(k>1 && v[h[k]]<v[h[k/2]]) {
        change(k,k/2);
        k/=2;
    }
}
void down(int k) {
    int son=0;
    int ls=2*k,rs=2*k+1;
    if(ls<=n) {
        son=ls;
        if(rs<=n && v[h[rs]]<v[h[ls]])
            son=rs;
        if(v[h[son]]>=v[h[k]])
            son=0;
    }
    if(son) {
        change(k,son);
        down(son);
    }
}
void del(int k) {
    change(k,n);
    n--;
    up(k);
    down(k);
}

void dijkstra(int node) {
    for(int i=0; i<(int)g[node].size(); i++) {
        graph aux=g[node][i];
        if(v[aux.n]>v[node]+aux.c) {
            v[aux.n]=v[node]+aux.c;
            up(pos[aux.n]);
        }
    }
    if(n>0) {
        int next=h[1];
        del(1);
        dijkstra(next);
    }
}

int main() {
    int nr;
    fin>>n>>m;
    nr=n;
    for(int i=1; i<=m; i++) {
        int x,y,c;
        fin>>x>>y>>c;
        graph aux;
        aux.n=y;
        aux.c=c;
        g[x].push_back(aux);
    }
    for(int i=1; i<=n; i++) {
        v[i]=INF;
        h[i]=i;
        pos[i]=i;
    }
    v[1]=0;
    del(1);
    dijkstra(1);
    for(int i=2; i<=nr; i++)
        fout<<v[i]<<" ";
    return 0;
}