#include <fstream>
#include <vector>
#include <deque>
#include <algorithm>
#include <climits>
#include <iomanip>
#include <queue>

#define MOD 666013
#define INT_MAX 1000000000

using namespace std ;

ifstream cin ("dijkstra.in") ;
ofstream cout ("dijkstra.out") ;

priority_queue<pair<int, int> > pq ;

vector<pair<int, int> > m[50009] ;

int d[50009] ;

void djk(int nod)
{
    pq.push({-1, nod}) ;

    while(pq.size())
    {
        int cost = pq.top().first ;
        int nod = pq.top().second ;

        pq.pop() ;

        if(cost > d[nod] || !d[nod])
        {

        d[nod] = cost ;

        for(int f = 0 ; f < m[nod].size() ; f ++)
        {
            int nnod = m[nod][f].first ;
            int ccost = m[nod][f].second ;

            if(!d[nnod])pq.push({cost - ccost, nnod}) ;
        }
        }
    }
}

int main()
{
    int n, q ;

    cin >> n >> q ;

    while(q --)
    {
        int a, b, c ;

        cin >> a >> b >> c ;

        m[a].push_back({b, c}) ;
    }

    djk(1) ;

    for(int f = 2 ; f <= n ; f ++)
        cout << d[f] * -1 -1 << " " ;

    return 0 ;
}
/// 1990