#include <bits/stdc++.h>
#define N 50005

using namespace std;

ifstream fin("dijkstra.in") ;
ofstream fout("dijkstra.out") ;

int n , m ;
vector<pair<int,int> > graf[N] ;
int dist[N] ;
bool viz[N] ;

class cmp
{
public:
    bool operator () ( int a , int b)
    {
        return dist[a] > dist[b] ;
    }
};

void citire()
{
    int i , x , y , z;
    fin >> n >> m ;
    for ( i = 1; i <= m ; i++ )
    {
        fin >> x >> y >> z;
        graf[x].push_back({y,z}) ;
    }
}

void dij()
{
    int i , nod ;
    priority_queue<int,vector<int>,cmp> pq ;
    pq.push(1) ;
    dist[1] = 0 ;
    for ( i = 2 ; i <= n ; i++ )
        dist[i] = 0x3f3f3f3f ;
    while ( !pq.empty() )
    {
        nod = pq.top() ;
        pq.pop() ;
        if ( viz[nod] == true )
            continue ;
        viz[nod] = true ;
        for ( auto vec : graf[nod] )
        {
            if ( dist[vec.first] > dist[nod] + vec.second )
            {
                dist[vec.first] = dist[nod] + vec.second ;
                pq.push(vec.first) ;
            }
        }
    }
    for ( i = 2 ; i <= n ; i++ )
    {
        if ( dist[i] == 0x3f3f3f3f )
            fout << "0 " ;
        else
            fout << dist[i] << " " ;
    }
}

int main()
{
    citire() ;
    dij();
}