#include <fstream>
#include <vector>
#include <queue>
#include <climits>

#define MOD 1000000007

using namespace std;

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

int n, q ;

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

int d[50009] ;

void lee(int k)
{
    priority_queue<pair<int, int> > pq ;

    for(int f = 1 ; f <= n ; f ++)
        d[f] = INT_MAX / 2 ;

    d[k] = -1 ;

    for(int f = 0 ; f < m[k].size() ; f ++)
        pq.push({m[k][f].second * -1, m[k][f].first}) ;

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

        pq.pop() ;

        if(d[nod] == INT_MAX / 2)
        {

        d[nod] = cost ;

        for(int f = 0 ; f < m[nod].size() ; f ++)
        {
            int newnod = m[nod][f].first ;
            int newcost = cost - m[nod][f].second ;

            pq.push({newcost, newnod}) ;
        }
        }

    }
}

int main()
{
    cin >> n >> q ;

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

        cin >> a >> b >> c ;

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

    lee(1) ;

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

    return 0 ;
}