//
//  main.cpp
//  dijkstra
//
//  Created by Tereza Oprea on 17/10/2018.
//  Copyright © 2018 Tereza Oprea. All rights reserved.
//

#include <iostream>
#include <fstream>
#define pii pair<int,int>
#define MAX 20010
#include <vector>
#include <queue>

using namespace std;

int dist[50010], x, y, c, m, n, first, price;

vector <pii> v[50010];

priority_queue<pii, vector<pii>, greater<pii> > cod;

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

int main() {
    fin >> n >> m;
    for (int i=1; i<=n; i++)
        dist[i] = MAX;
    for (int i=1; i<=m; i++)
    {
        fin >> x >> y >> c;
        v[x].push_back({c, y});
    }
    cod.push({0, 1});
    while (!cod.empty())
    {
        first = cod.top().second;
        price = cod.top().first;
        if (dist[first] < MAX)
        {
            cod.pop();
            continue;
        }
        dist[first] = price;
        cod.pop();
        for (auto it: v[first])
        {
            if (dist[it.second] == MAX)
            {
                cod.push({it.first + price, it.second});
            }
        }
    }
    for (int i=2; i<=n; i++)
        fout << dist[i] << ' ';
    return 0;
}