/*
 * =====================================================================================
 *
 *       Filename:  dijkstra.cpp
 *
 *    Description:  
 *
 *         Author:  Victor Carbune ([email protected])
 *	     Info:  Grupa 325, Seria CA
 *
 * =====================================================================================
 */

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>

#define INF 1000000

using namespace std;

vector<pair<int, int> > *graf;
int n, m, *d;

void read_data()
{
    int x, y, cost;
    
    scanf("%d %d", &n, &m);
    graf = new vector<pair<int, int> >[n];
    
    for (int i = 0; i < m; i++) {
        scanf("%d %d %d", &x, &y, &cost);
        x--, y--;
        graf[x].push_back(make_pair(y, cost));
    }
}

void dijkstra(int s)
{
    int nod, dst, cost, v;

    priority_queue<pair<int, int>, vector<pair <int, int> >, greater< pair<int, int> > > Q;

    d = new int[n];
    
    for (int i = 0; i < n; i++)
        d[i] = INF;

    d[s] = 0;
    Q.push(make_pair(d[s], s));

    while (!Q.empty()) {
        dst = Q.top().first;
        nod = Q.top().second;
        
        Q.pop();

        if (dst <= d[nod])
            for (unsigned int i = 0; i < graf[nod].size(); i++) {
                v = graf[nod][i].first;
                cost = graf[nod][i].second;

                // relaxare
                if (d[v] > d[nod] + cost) {
                    d[v] = d[nod] + cost;
                    Q.push(make_pair(d[v], v));
                }
            }
    }
}


int main() {
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    read_data();
    dijkstra(0);

    for (int i = 1; i < n; i++)
        printf("%d ", d[i]);
    printf("\n");
    return 0;
}