#include <iostream>
#include <fstream>
#include <vector>
#include <set>
#define mp make_pair
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];
int dist[maxN];

int main() {

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

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

    set <pair<int,int> > d;
    d.insert(mp(0, 1));
    while(! d.empty()) {
        int node = d.begin()-> second;
        d.erase(d.begin());

        for(auto v : g[node]) {
            int nod = v.first;
            int cost = v.second;
            if(dist[nod] > dist[node] + cost) {
                // relaxam distanta de la "node" la "nod"
                if(dist[nod] != INF)
                    d.erase(d.find(mp(dist[nod], nod)));
                dist[nod] = dist[node] + cost;
                d.insert(mp(dist[nod], nod));
            }
        }
    }

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

    return 0;
}