#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream in ("dijkstra.in");
ofstream out ("dijkstra.out");
vector<pair<int,int>>g[100005];
priority_queue< pair<int,int>,vector<pair<int,int>>, greater<pair<int,int> >  >q;

int sel[100005],t[100005],d[100005];
void djk (int pl)
{
    sel[pl]=1;
    d[pl]=0;
    for(auto i : g[pl] )
    {
        d[i.second]=i.first;
        q.push({i.first,i.second});
    }
    while(!q.empty())
    {
        while(!q.empty()&&sel[q.top().second])
        {
            q.pop();
        }
        if(q.empty())
        {
            break;
        }
        int    k1=q.top().first;
        int  k=q.top().second;
        sel[k]=1;
        for(auto i:g[k])
        {
            if(d[i.second]>d[k]+i.first)
            {
                d[i.second]=d[k]+i.first;
                q.push({d[i.second],i.second}) ;
            }
        }
    }

}
int n,i,j,m,x,y,c,N,gg,ma=0,G;
int main()
{
    in>>n>>m;
    for(i=1; i<=m; i++)
    {
        in>>x>>y>>c;

        g[x].push_back({c,y});
        if(ma<x)ma=x;
            if(ma<y)ma=y;
    }
    n=ma;
    for(i=1; i<=n; i++)
    {
        d[i]=9999999;

    }

    djk(1);
    for(i=2;i<=n;i++)out<<d[i]<<" ";
    return 0;
}