#include <cstdio>
#include <vector>
using namespace std;
#define MAX 50001
#define INF 2000000000
vector <pair<int, int> > lista[MAX];
int n, m, d[MAX], pred[MAX], heap[MAX], poz[MAX], nh;
void dijkstra(int st);
void upheap(int nod);
void sterge(int nod);
void downheap(int nod);
void schimba(int poza, int pozb);
int main()
{
    int i, x, y, w;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i=1; i<=m; i++){
        scanf("%d%d%d", &x, &y, &w);
        lista[x].push_back(make_pair(y, w));
    }
    dijkstra(1);
    for(i=2; i<=n; i++){
        if(d[i]==INF) d[i] = 0;
        printf("%d ", d[i]);
    }
    return 0;
}
void dijkstra(int st){
    int i, nod, y, w;
    for(i=1; i<=n; i++){
        d[i] = INF;
        pred[i] = 0;
        heap[i] = i;
        poz[i] = i;
    }
    heap[1] = st; heap[st] = 1;
    poz[1] = st; poz[st] = 1;
    d[st] = 0;
    nh = n;
    while(nh>0){
        nod = heap[1];
        if(d[nod]==INF) break;
        sterge(1);
        for(i=0; i<lista[nod].size(); i++){
            int y = lista[nod][i].first;
            int w = lista[nod][i].second;
            if(d[nod]+w<d[y]){
                d[y] = d[nod]+w;
                pred[y] = nod;
                upheap(poz[y]);
            }
        }
    }
}
void upheap(int nod){
    if(nod==1) return;
    int tata = nod/2;
    if(d[heap[tata]]>d[heap[nod]]){
        schimba(tata, nod);
        upheap(tata);
    }
}
void schimba(int poza, int pozb){
    swap(heap[poza], heap[pozb]);
    poz[heap[poza]] = pozb;
    poz[heap[pozb]] = poza;
}
void sterge(int nod){
    schimba(nod, nh);
    nh--;
    downheap(nod);
}
void downheap(int nod){
    if(nod*2>nh) return;
    int fiumin = nod*2;
    if(nod*2+1<=nh and d[heap[fiumin]]>d[heap[2*n+1]])
        fiumin = 2*n+1;
    if(d[nod]>d[fiumin]){
        schimba(nod, fiumin);
        downheap(fiumin);
    }
}