#include <fstream>
#include <vector>
#include <climits>
#include <queue>
#define PII pair < int, int >

using namespace std ;

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

const int MAXVAL = 5e5 + 5 ;

int n, m ;
vector < vector < PII > > graph ;

void solve ()
{

    int g = graph.size() ;

    vector < int > d(g + 1, INT_MAX) ;
    d[1] = 0 ;

    priority_queue <PII, vector < PII >, greater < PII > > q ;

    q.push ({1, 0}) ;

    while (!q.empty())
    {

        int top = q.top().first ;
        int top_w = q.top().second ;
        q.pop() ;

        if (top_w > d[top])
            continue ;

        for (auto item : graph[top])
        {

            int x = item.first ;
            int weight = item.second ;

            if (d[x] > d[top] + weight)
                d[x] = d[top] + weight, q.push ({x, d[x]}) ;

        }

    }

    for (int i = 2 ; i <= n ; i ++)
    {

        if (d[i] == INT_MAX)
            cout << 0 << ' ' ;

        else
            cout << d[i] << ' ' ;

    }

}

int main()
{

    int x, y, weight ;

    cin >> n >> m ;

    graph.resize (n + 1) ;

    for (int i = 1 ; i <= m ; i ++)
        cin >> x >> y >> weight, graph[x].push_back ({y, weight}) ;

    solve () ;

    return 0 ;

}