#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 50001;

int N, M;

typedef pair<int, int> intPair;
vector<intPair> A[NMAX];
priority_queue<intPair, vector<intPair>, greater<intPair> > PQ;
int distMin[NMAX];

void dijkstra(int X) {
    PQ.push(make_pair(0, X));
    distMin[X] = 0;
    while(!PQ.empty()) {
        int U = PQ.top().second;
        PQ.pop();

        for(auto i: A[U]) {
            int V = i.first,
                W = i.second;
            if(distMin[V] > distMin[U] + W) {
                distMin[V] = distMin[U] + W;
                PQ.push(make_pair(distMin[V], V));
            }
        }
    }
}

int main()
{
    in >> N >> M;
    int a, b, c;
    for(int i = 1; i <= M; i++) {
        in >> a >> b >> c;
        A[a].push_back(make_pair(b, c));
    }

    for(int i = 1; i <= N; i++)
        distMin[i] = (1 << 25);

    dijkstra(1);

    for(int i = 2; i <= N; i++)
        out << distMin[i] << ' ';
    return 0;
}