#include <bits/stdc++.h>

using namespace std;
#define per pair<int,int>
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
const int N=50001;
priority_queue<per> pq;
vector<per> v[N];
int dist[N],vc[N];
int main()
{
    int p,n,i,x,y,z,nod,m,nod2,cost;
    fin>>n>>m;
    while(fin>>x>>y>>z){
        v[x].push_back({z,y});
    }
    for(i=1;i<=n;i++)
        dist[i]=INT_MAX;
    dist[1]=0;
    pq.push({0,1});
    while(!pq.empty())
    {
        nod=pq.top().second;
        pq.pop();
        if(!vc[nod]){
            vc[nod]=1;
            m=v[nod].size();
            for(i=0;i<m;i++)
            {
                cost=v[nod][i].first;
                nod2=v[nod][i].second;
                if(dist[nod2]>dist[nod]+cost)
                {
                    dist[nod2]=dist[nod]+cost;
                    pq.push({-dist[nod2],nod2});
                }
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]==INT_MAX)
            fout<<"0 ";
        else
            fout<<dist[i]<<" ";
    }
    return 0;
}