#include <bits/stdc++.h>

using namespace std;

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

const int MAXN = 50003, MAXM = 250003, INF = 30000;

int n, m, dist[MAXN];
vector<pair<int, int> > adj[MAXN];

int main()
{
    fin >> n >> m;
    for(int i = 1, x, y, z; i <= m; i++)
    {
        fin >> x >> y >> z;
        adj[x].push_back({y, z});
    }
    for(int i = 1; i <= n; i++) dist[i] = INF;
    dist[1] = 0;

    set<pair<int, int> > h;
    h.insert({0, 1});
    while(!h.empty())
    {
        int node = h.begin()->second;
        int d = h.begin()->first;
        h.erase(h.begin());

        for(auto& it : adj[node])
        {
            int to = it.first;
            int cost = it.second;

            if(dist[to] > dist[node] + cost)
            {
                if(dist[to] != INF) h.erase({dist[to], to});
                dist[to] = dist[node] + cost;
                h.insert({dist[to], to});
            }
        }
    }

    for(int i = 2; i <= n; i++)
        fout <<  (dist[i] == INF ? 0 : dist[i]) << " ";

    return 0;
}