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

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

struct comp
{
    int nod, cost;
    bool operator < (const comp &x) const
    {
        return cost > x.cost;
    }
};

const int NMAX = 50005, INF = 1e9;
vector<pair<int,int>>adj[NMAX];
priority_queue<comp>pq;
int n, m, dist[NMAX];
bool viz[NMAX];

inline void solve()
{
    for(int i = 2; i <= n; ++ i)
        dist[i] = INF;
    pq.push({1, 0});
    while(!pq.empty())
    {
        int node = pq.top().nod;
        pq.pop();
        if(viz[node])
            continue;
        viz[node] = 1;
        for(auto x : adj[node])
        {
            int new_node = x.first;
            int new_cost = x.second;
            if(dist[node] + new_cost < dist[new_node])
            {
                dist[new_node] = dist[node] + new_cost;
                pq.push({new_node, dist[new_node]});
            }
        }
    }
    for(int i = 2; i <= n; ++ i)
    {
        if(dist[i] == INF)
            fout << 0 << ' ';
        else
            fout << dist[i] << ' ';
    }
}

int main()
{
    fin >> n >> m;
    for(int i = 1; i <= m; ++ i)
    {
        int node1, node2, cost;
        fin >> node1 >> node2 >> cost;
        adj[node1].push_back({node2, cost});
    }
    solve();
}