#include<fstream>
#include<iostream>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
const long long inf = 1e9+1;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int NMAX = 50001;
int start;
ll dist[NMAX];//dist[i]=distanta minima de la nodul de start la nodul i
struct elem {
    int nod;
    int cost;
    elem(int nodCrt, int c) :nod(nodCrt), cost(c) {};
};
vector<vector<elem>>graph;


struct alese {
    bool operator ()(int a, int b) {
        return dist[a] > dist[b];
    }
};
void dijkstra(int n) {
    priority_queue<ll, vector<ll>, alese>pq;

    pq.push(1);
    int crt;

    ll alt;
    while (!pq.empty())
    {
        crt = pq.top();
        pq.pop();

        for (auto v : graph[crt]) {
            alt = dist[crt] + v.cost;
            if (alt < dist[v.nod]) {
                dist[v.nod] = alt;
                pq.push(v.nod);
            }
        }
    }
    return;

}

int main() {
    int n, m;
    fin >> n >> m;
    graph.resize(n + 1);
    int firstNod, secondNod, cost;
    for (int i = 0; i < m; ++i) {
        fin >> firstNod >> secondNod >> cost;
        graph[firstNod].push_back(elem(secondNod, cost));//nu e si invers pentru ca zice ca este "graf orientat"
    }
    for (int i = 0; i <= n; ++i) {
        dist[i] = inf;
    }
    dist[1] = 0;//distanta de la nodul de start la el insusi este 0
    dijkstra(n);
    for (int i = 2; i <= n; ++i) {
        if (dist[i] == inf) {
            fout << 0 << " ";
        }
        else {
            fout << dist[i] << " ";
        }
    }
    return 0;
}