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

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

const int maxN = 50005;
const int INF = 1e9;

vector <pair<int,int>> g[maxN];
int d[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)
        d[i] = INF;

    set <pair<int,int>> s;
    s.insert({0, 1});
    d[1] = 0;
    while(s.size()) {
        pair<int,int> x = *(s.begin());
        s.erase(s.begin());

        int node = x.second;
        int distNode = x.first;

        if(d[node] < distNode)
            continue;

        for(auto next : g[node]) {
            int cost = next.second;
            int to = next.first;

            if(d[to] > distNode + cost) {
                d[to] = distNode + cost;
                s.insert({d[to], to});
            }
        }
    }

    for(int i = 2; i <= n; ++i)
        fout << d[i] << " ";

    return 0;
}