#include <bits/stdc++.h>
using namespace std;
using PII = pair<int, int>;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int nr_noduri, nr_muchii, dist[50001];
unordered_map<int, bool> visited;
vector<vector<PII>> graf;


int main()
{
    fin >> nr_noduri >> nr_muchii;
    graf.resize(nr_noduri + 1);
    for (int i = 1; i <= nr_noduri; i++)
    {
        int n1, n2, cost;
        fin >> n1 >> n2 >> cost;
        graf[n1].push_back(make_pair(cost, n2));
    }

    for (int i = 1; i <= nr_noduri; i++)
        dist[i] = INT_MAX;

    dist[1] = 0;
    priority_queue<PII, vector<PII>, greater<PII>> optim;
    optim.push(make_pair(0, 1));

    while(!optim.empty())
    {
        PII curr = optim.top();
        optim.pop();
        if (visited[curr.second] == 1)
            continue;
        visited[curr.second] = 1;
        for (auto next:graf[curr.second])
            if (next.first + dist[curr.second] < dist[next.second])
                dist[next.second] = next.first + dist[curr.second],
                optim.push(make_pair(next.first, next.second));
    }

    for (int i = 2; i <= nr_noduri; i++)
         fout << dist[i] << " ";

    return 0;
}