#include <fstream>
#include <vector>
#include <queue>

using namespace std;

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

const int Nmax = 50005;

struct muchie{
    int nod, cost;
};

struct nod{
    int dist;
    vector<muchie> vecini;
};

class cmp{
public:
    bool operator()(muchie a, muchie b){
        return a.cost > b.cost;
    }
};

int n, m;
nod noduri[Nmax];
priority_queue<muchie, vector<muchie>, cmp> pq;

void citire(){
    int nod1, nod2, cost;

    fin >> n >> m;
    for(int i = 1; i <= m; i++){
        fin >> nod1 >> nod2 >> cost;

        noduri[nod1].vecini.push_back({nod2, cost});
    }
}

void preinit_distante(){
    for(int i = 1; i <= n; i++){
        noduri[i].dist = -1;
    }
}

void dijkstra(){
    int nod, cost;

    pq.push({1, 0});

    while(!pq.empty()){
        nod = pq.top().nod;
        cost = pq.top().cost;
        pq.pop();

        if(noduri[nod].dist == -1){
            noduri[nod].dist = cost;

            for(muchie vecin : noduri[nod].vecini){
                if(noduri[vecin.nod].dist == -1){
                    pq.push({vecin.nod, noduri[nod].dist + vecin.cost});
                }
            }
        }
    }
}

void afisare(){
    for(int i = 2; i <= n; i++){
        if(noduri[i].dist == -1){
            noduri[i].dist = 0;
        }

        fout << noduri[i].dist << " ";
    }
}

int main(){
    citire();

    preinit_distante();
    dijkstra();

    afisare();

    return 0;
}