#include <bits/stdc++.h>
#define dim 50005
#define inf int(1e9)
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
priority_queue < pair < int, int >,vector < pair < int, int > >,greater < pair < int, int > > > q;
struct dijkstra
{
    int cost,x;
};
vector <dijkstra> graph[dim];
int n,m,dist[dim];
void Read()
{
    f>>n>>m;
    for(int i=1;i<=m;++i)
    {
        int x,y,cost;
        f>>x>>y>>cost;
        graph[x].push_back({cost,y});
    }
}
void Dijkstra()
{
    q.push({0,1});
    for(int i=2;i<=n;++i)dist[i]=inf;
    while(!q.empty())
    {
        int node=q.top().second;
        int cost=q.top().first;
        q.pop();
        if(cost!=dist[node])continue;
        for(int i=0;i<graph[node].size();++i)
        {
            int son=graph[node][i].x,path=graph[node][i].cost;
            if(dist[son]>dist[node]+path)
            {
                dist[son]=dist[node]+path;
                q.push({dist[son],son});
            }
        }
    }
    for(int i=2;i<=n;++i)
        g<<dist[i]<<" ";
}
int main()
{
    Read();
    Dijkstra();
    return 0;
}