#include <stdio.h>
#include <vector>
#include <queue>
#include <utility>
#include <list>
using namespace std;

#define inf 10000000

typedef pair<int, int> pereche;

vector < list<pereche> > graf;
list <pereche>::iterator it, last;
vector <int> dist;
vector <bool> vizitat;

struct compare{
    bool operator() (pereche i, pereche j){
        return i.second > j.second;
    }
};

priority_queue < pereche, vector<pereche>, compare> heap;
int n, m, start = 1;

void citire(){
    freopen("dijkstra.in", "r", stdin);
    int x, y, c, j;
    char cc[100];
    scanf("%i %i", &n, &m);

    graf.resize(n+1);
    dist.resize(n+1, inf);
    vizitat.resize(n+1);

    fgets(cc, 100 ,stdin);

    for(int i = 1; i <= m; ++i){
        fgets(cc, 100 ,stdin);
        x = y = c = j = 0;

        while(cc[j] != ' ') x = x*10 + cc[j++] - '0';
        j++;
        while(cc[j] != ' ') y = y*10 + cc[j++] - '0';
        j++;
        while(cc[j] != '\n') c = c*10 + cc[j++] - '0';

        graf[x].push_back(pereche(y, c));
    }
    fclose(stdin);
}

void dijkstra(){
    int nod, cost;
    pereche top;

    heap.push( pereche(1,0) );
    dist[1] = 0;

    while(!heap.empty()){
        top = heap.top();
        heap.pop();

        it = graf[top.first].begin();
        last = graf[top.first].end();

        if(!vizitat[top.first]){
            for(; it != last; ++it){
                nod = it->first; cost = it->second;

                if(dist[nod] > cost + dist[top.first]){
                    dist[nod] = cost + dist[top.first];
                    heap.push( pereche(nod, dist[nod]) );
                }
            }
            vizitat[top.first] = 1;
        }
    }
}

void afisare(){
    for(int i = 2; i <= n; ++i)
        printf("%i ", (dist[i] != inf) ? dist[i] : 0);
    fclose(stdout);
}

int main(){
    freopen("dijkstra.out", "w", stdout);
    citire();
    dijkstra();
    afisare();

    return 0;
}