#include <bits/stdc++.h>

using namespace std;

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

int n , m , dist[50001] ;
vector<pair<int,int> > graf[50001] ;

class compar
{
public:
    bool operator () ( const int &a , const int &b )
    {
        return dist[a] > dist[b] ;
    }
};
void citire()
{
    int i , x , y , c ;
    fin >> n >> m ;
    for ( i = 1 ; i <= m ; i++ )
    {
        fin >> x >> y >> c ;
        graf[x].push_back(make_pair(y,c)) ;
    }
}

void dijkstra()
{
    int i , nod , nr ;
    priority_queue<int,vector<int> , compar > pq ;
    pq.push(1) ;
    memset(dist,0x3f3f3f3f,4*n+4) ;
    dist[1] = 0 ;
    while(!pq.empty())
    {
        nod = pq.top() ;
        pq.pop() ;
        nr = graf[nod].size() ;
        for ( i = 0 ; i < nr ; i++ )
        {
            if ( dist[graf[nod][i].first] > dist[nod] + graf[nod][i].second )
            {
                dist[graf[nod][i].first] = dist[nod] + graf[nod][i].second ;
                pq.push(graf[nod][i].first) ;
            }
        }
    }
    for ( i = 2 ; i <= n ; i++ )
    {
        if ( dist[i] == 0x3f3f3f3f )
            fout << "0 " ;
        else
            fout << dist[i] << " " ;
    }
}

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