#include <iostream>
#include <vector>
#include <set>
#include <fstream>
using namespace std;

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

const int maxN = 5e4 + 5;
const int INF = 1e9;

vector <pair <int,int> > g[maxN];
set <pair <int,int> > d;
int dist[maxN];

int main() {

    int n, m; fin >> n >> m;

    for(int i = 1; i <= m; ++i) {
        int u, v, c;
        fin >> u >> v >> c;
        g[u].push_back({v, c});
    }

    for(int i = 1; i <= n; ++i) dist[i] = INF;

    d.insert({0, 1});
    dist[1] = 0;

    while(d.size() != 0) {
        pair <int, int> Front = *(d.begin());

        int node = Front.second;
        int DistAct = Front.first;

        d.erase(d.begin());

        if(dist[node] < DistAct) { continue; }

        for(auto v : g[node])
            if(dist[v.first] > DistAct + v.second) {
                dist[v.first] = DistAct + v.second;
                d.insert({dist[v.first], v.first});
            }
    }

    for(int i = 2; i <= n; ++i)
        if(dist[i] == INF) fout << "0 ";
        else fout << dist[i] << " ";

    return 0;
}