#include <cstdio>
#include <vector>
#include <bitset>
#include <queue>
#include <iostream>

using namespace std;

#define inf 0x3f3f3f3f

typedef struct{

    int vecin;
    int cost;

} nod;

vector < vector <nod> > Graf;
vector <int> dist;
queue <int> Q;

int N, M;
int a, b, c;

void citire(){

    freopen("dijkstra.in", "r", stdin);

    scanf("%d %d", &N, &M);

    Graf.resize(N+1);

    for(; M; M--){

        scanf("%d %d %d", &a, &b, &c);

        nod x = {b, c};

        Graf[a].push_back(x);
    }
}

void dijkstra(){

    dist.resize(N+1, inf);
    dist[1] = 0;
    Q.push(1);

    while(!Q.empty()){

        int current = Q.front();
        Q.pop();

        vector <nod> ::iterator it;

        for(it = Graf[current].begin(); it != Graf[current].end(); ++it)
            if(dist[it->vecin] > dist[current] + it->cost)
                Q.push(it->vecin),
                dist[it->vecin] = dist[current] + it->cost;
    }
}

void afis(){

    freopen("dijkstra.out", "w", stdout);

    for(int i = 2; i<=N; i++)
        printf("%d ", dist[i] < inf ? dist[i] : 0);
}

int main(){

    citire();
    dijkstra();
    afis();

    return 0;
}