#include <bits/stdc++.h>
using namespace std;
      
ifstream in("dijkstra.in");
ofstream out("dijkstra.out");

const int inf = 1e9;

vector< vector< pair< int, int > > > G;
vector< int > dist;

void Dijkstra(int nod) {
    set< pair< int, int > > s;
    s.insert({0, nod});
    dist[nod] = 0;

    while(!s.empty()) {
        int tempNode = s.begin()->second;
        int tempDist = -s.begin()->first; s.erase(s.begin());

        if(tempDist > dist[tempNode]) {
            continue;
        }

        for(auto vecin: G[tempNode]) {
            if(dist[tempNode] + vecin.second < dist[vecin.first]) {
                s.erase({dist[vecin.first], vecin.first});
                dist[vecin.first] = dist[tempNode] + vecin.second;
                s.insert({-dist[vecin.first], vecin.first});
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); in.tie(0); out.tie(0);
 
    int n, m; in >> n >> m;

    G.resize(n); dist.resize(n, inf);
    for(int i = 1; i <= m; ++i) {
        int x, y, cost; in >> x >> y >> cost;
        --x; --y;
        G[x].push_back({y, cost});
    }

    Dijkstra(0);

    for(int i = 1; i < n; ++i) {
        if(dist[i] != inf) {
            out << dist[i] << " ";
        } else {
            out << "0 ";
        }
    }
 
    in.close(); out.close();
      
    return 0;
}