#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
#define MAX 50001
#include <bitset>
#define INF INT_MAX
using namespace std;
 
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
 
int n, m, dist[MAX], T[MAX], s[MAX];
 
bitset < MAX > viz;
 
vector < pair < int , int > > v[MAX];
 
priority_queue < pair< int , int > > heap;
 
void init()
    {
        for(int i=1; i<=n; i++)
            dist[i]=INF;
    }
 
void read()
    {
        f>>n>>m;
        int x, y, cost;
        for(int i=1; i<=m; i++)
        {
            f>>x>>y>>cost;
            v[x].push_back(make_pair(y, cost));
        }
    }
 
void djk()
    {
        init();
 
        heap.push(make_pair(0, 1));
 
        dist[1]=0;
 
        while(!heap.empty())
        {
            int node = heap.top().second;
 
            heap.pop();
 
            if(viz[node]==0)
            {
                viz[node]=1;
                for(size_t i=0; i<v[node].size(); i++)
                {
                    int p = v[node][i].first;
                    int cost = v[node][i].second;
                    if(dist[p]>dist[node]+cost)
                    {
                        dist[p]=dist[node]+cost;
                        T[p] = node;
                        heap.push(make_pair(-dist[p], p));
                    }
                }
 
            }
 
 
        }
 
    }
 
void afis()
    {
        for(int i=2; i<=n; i++)
            if(dist[i]==INF)
                g<<0<<" ";
            else g<<dist[i]<<" ";
    }
 
int main()
{
    read();
    djk();
    afis();
    return 0;
}