#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> p;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int viz[100001];
vector<pair<int,int>>graf_d[50001];
int distanta_dijkstra[50001];
void citire_dijkstra()
{
    int N,M;
    fin>>N>>M;
    for(int i=0;i<M;i++)
    {
        int x,y,z;
        fin>>x>>y>>z;
        graf_d[x].push_back(make_pair(y,z));
    }
    for(int i=1;i<=N;i++)
        distanta_dijkstra[i]=INT_MAX;
    
    distanta_dijkstra[1]=0;
    priority_queue<p,vector<p>,greater<p>>heap;
    heap.push(make_pair(0,1));
    
    for(int i=1;i<=N;i++)
        viz[i]=0;
    while(!heap.empty())
    {
        int current=heap.top().second;
        heap.pop();
        if(viz[current]==1)
            continue;
        else
            viz[current]=1;
        for(auto x:graf_d[current])
            if(distanta_dijkstra[current]+x.second < distanta_dijkstra[x.first])
            {
                distanta_dijkstra[x.first]=distanta_dijkstra[current]+x.second;
                heap.push(make_pair(distanta_dijkstra[x.first],x.first));
            }
    }
    for(int i=2;i<=N;i++)
        if(distanta_dijkstra[i]!=INT_MAX)
            fout<<distanta_dijkstra[i]<<" ";
        else
            fout<<0<<" ";
}
int main()
{
   citire_dijkstra();
}