#include <stdio.h>
#include <vector>
#define DIM 50010
using namespace std;
int n, m, v[DIM], d[DIM], x, y, i, j, c, minim, pminim;
const int INF=(1<<30);

struct dijkstra{
    int v, c;
};

vector<dijkstra> L[DIM];
dijkstra aux;
/*
void graf(int x){
    int i, poz=0, minim=(1<<30);
    v[x]=1;
    for(i=0; i<L[x].size(); i++)
    {
        int k=L[x][i].v;
        if(v[k]==0)
            d[k]=d[x]+L[x][i].c;
    }
    for(i=1; i<=n; i++)
        if(v[i]==0 && minim>d[i])
        {
            minim=d[i];
            poz=i;
        }
    if(poz!=0)
        graf(poz);
}
*/

int main(){
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d %d", &n, &m);
    for(i=1; i<=n; i++)
        d[i]=INF;
    d[1] = 0;
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        aux.v=y;
        aux.c=c;
        L[x].push_back(aux);
    }
//    graf(1);

    while (1) {
        minim = INF;
        for (i=1;i<=n;i++) {
            if (v[i] == 0 && d[i] < minim) {
                minim = d[i];
                pminim = i;
            }
        }
        if (minim == INF) {
            break;
        }
        // nodul pminim e cel lacare am gasit drumul minim, il marchez
        //si vad ce pot updata din el (noduri nealese inca)
        v[pminim]  = 1;
        for (i=0;i<L[pminim].size();i++) {
            int vecin = L[pminim][i].v;
            int cvecin = L[pminim][i].c;
            if (v[vecin] == 0 && d[vecin] > d[pminim] + cvecin)
                d[vecin] = d[pminim] + cvecin;

        }

    }


    for(i=2; i<=n; i++)
        if(d[i]==INF)
            printf("0 ");
        else
            printf("%d ", d[i]);
    printf("\n");
    return 0;
}