#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std ;

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

typedef pair<int , int> ii ;


const int NMAX = 260000 ;
const int INF = (1 << 30)-1;
int n , m , p , x , y , cost;
int d[NMAX]  ;

vector<ii> g[NMAX] ;

struct comp {
    bool operator()(ii x , ii y) {
        return x.second < y.second ;
    }
};

void init() {
    for(int i = 1 ; i<=n ; i++) {
        d[i] = INF ;
    }
}

priority_queue<ii , vector<ii> , comp> pq ;

void dijkstra(int nod) {

    d[nod] = 0;
    pq.push({nod , 0}) ;


    while (!pq.empty()) {

        int x , cost ;
        
        x = pq.top().first ;
        cost = pq.top().second ;
        pq.pop() ;

        if(d[x] != cost) continue;

        for(auto y : g[x]) {

            if(cost + y.second < d[y.first]) {

                d[y.first] = cost + y.second ;
                pq.push({y.first , d[y.first]}) ;
            }
        }
    }
}

int main()
{

    fin >> n >> p;
    while(fin >> x >> y >> cost) {

        g[x].push_back({y , cost}) ;
        //g[y].push_back({x , cost}) ;
    }

    init() ;
    dijkstra(1) ;

    for(int i = 2 ; i<=n ; i++) {
        if(d[i] == INF )
            fout << -1 << " " ;
        else fout << d[i] << ' ' ;
    }
    return 0;
}