#include <bits/stdc++.h>
using namespace std;

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

#define INF 2e6 + 5
typedef pair <int, int> ipair;
priority_queue <ipair,vector<ipair>,greater<ipair> > q;
int n, m;

int main()
{
    in >> n >> m;

    vector <ipair> a[n + 1];
    vector <bool> seen (n + 1, false);
    vector <int> dist(n + 1, INF);

    for(int i = 1; i <= m; ++ i)
    {
        int x, y, cost;
        in >> x >> y >> cost;
        a[x].push_back({cost, y});
    }

    dist[1] = 0;
    for(auto i : a[1])
    {
        q.push(i);
        dist[i.second] = i.first;
    }
    seen[1] = true;

    while(!q.empty())
    {
        while(!q.empty() && seen[q.top().second])
            q.pop();

        if(!q.empty())
        {
            int current = q.top().second;
            seen[current] = true;
            q.pop();

            for(auto i : a[current])
            {
                int next = i.second;
                int weight = i.first;
                q.push(i);

                if(dist[current] + weight < dist[next])
                    {
                        dist[next] = dist[current] + weight;
                        q.push({dist[next], next});
                    }
            }
        }
    }

    for(int i = 2; i <= n; ++ i)
    {
        if(dist[i] == INF)
            out << 0 << ' ';
        else
            out << dist[i] << ' ';
    }

    return 0;
}