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

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

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

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

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

    while(optim.size() > 0)
    {
        PII curr = optim.top();
        optim.pop();
        if (visited[curr.second] == 1)
            continue;
        visited[curr.second] = 1;
        for (PII &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(dist[next.second], next.second));
    }

    for (int i = 2; i <= nr_noduri; i++)
    {
        if (dist[i] == LONG_LONG_MAX)
            dist[i] = 0;
        fout << dist[i] << " ";
    }


    return 0;
}