#include <bits/stdc++.h>
#define mp std::make_pair
#define index second
#define cost first
#define dimn 50005
using nod = std::pair <int, int>;
const int inf = 20005;

std::ifstream f("dijkstra.in");
std::ofstream g("dijkstra.out");

int N;
std::set <nod> vec[dimn];
int dist[dimn];

void dijkstra(int src=1) {
    for (int i=0; i<=N; i++) dist[i] = inf;

    std::priority_queue <nod, std::vector <nod>, std::greater <nod>> pq;
    pq.push(mp(0, src)); dist[src] = 0;
    nod pres, nou;

    while(!pq.empty()) {
        pres = pq.top();
        pq.pop();

        for (auto it:vec[pres.index]) {
            nou = it;
            if(dist[nou.index] > dist[pres.index] + nou.cost) {
                dist[nou.index] = dist[pres.index] + nou.cost;
                pq.push(mp(dist[nou.index], nou.index));
            }
        }
    }
}

void citire() {
    f >> N;
    int m; f >> m;
    for (int i=0, c, y, x; i<m; i++) {
        f >> x >> y >> c;
        vec[x].insert(mp(c, y));
    }
}
void rezolvare() {
    dijkstra();
    for (int i=2; i<=N; i++)
        g << dist[i] << " " ;
}

int main()
{
    citire();
    rezolvare();

    return 0;
}