#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define v first
#define in second
using namespace std;

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

const int NMAX = 5e4+1;
const long long MAX = 25e4*2e4+1;


struct arc{

    int d, c;

};

priority_queue < pair<long long,long long> > pq;
bitset <NMAX> b;

long long dji[NMAX];
vector <arc> g[NMAX];
int n , s;


void djikstra(int s){

    pair <int,int> x;
    x.in = s;
    x.v = 0;

    pq.push(x);

    while(!pq.empty()){

        pair <int,int> x = pq.top();
        pq.pop();
        if(b[x.in]) continue;

        x.v = x.v*(-1);

        dji[x.in] = x.v;
        b[x.in] = 1;

        int l = g[x.in].size();

        for(int i = 0 ; i < l ; i++){

            int vec = g[x.in][i].d;
            int cost = g[x.in][i].c;

            if(!b[vec] && dji[vec]>dji[x.in]+cost){
                pair <int,int> y;
                y.in = vec;
                y.v = (dji[x.in]+cost) * (-1);
                dji[vec] = dji[x.in]+cost;
                pq.push(y);
            }

        }

    }

}

void afis(){

    for(int i = 2 ; i <= n ; i++){
        if(dji[i] == MAX) dji[i] = -1;
        cout << dji[i] << ' ';
    }

}

int main()
{
    int a , b , c , m;

    cin >> n >> m;

    for(int i = 1 ; i <= n ; i++){
        dji[i] = MAX;
    }

    while(m--){

        cin >> a >> b >> c;

        arc x;
        x.d = b;
        x.c = c;

        g[a].push_back(x);
    }

    djikstra(1);

    afis();

    return 0;
}