#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() (const int &i, const int &j){
        return dist[i] > dist[j];
    }
};

priority_queue < int, vector<int>, compare> coada;
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(){
    unsigned int top, nod, cost;
    coada.push(start);
    dist[start] = 0;
    vizitat[start] = 1;

    while(!coada.empty()){
        top = coada.top();
        coada.pop();
        vizitat[top] = 0;

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

        for(; it != last; ++it){
            nod = it->first; cost = it->second;

            if(dist[nod] > cost + dist[top]){
                dist[nod] = cost + dist[top];
                if(!vizitat[nod])
                    coada.push(nod), vizitat[nod] = 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;
}