#include <fstream>
#include <vector>
#include <queue>
#define lim 10000

std::ifstream f ("date.in");
std::ofstream g ("date.out");

using namespace std;

const int oo = (1 << 30);

int n, m;
int distante[lim];
bool inCoada[lim];

vector<pair<int, int>>graf[lim];

struct compara {
    bool operator()(int x, int y) {
        return distante[x] > distante[y];
    }
};

priority_queue<int, vector<int>, compara>coada;

void read();
void init(int nodStart);
void dijkstra(int nodStart);
void print();

int main() {
    read();
    init(1);
    dijkstra(1);
    print();
    return 0;
}

void read() {
    f>>n>>m;
    for (int i=1;i<=n;++i) {
        pair<int, int>el;
        int costMuchie;
        f>>el.first>>el.second>>costMuchie;
        graf[el.first].push_back(make_pair(el.second, costMuchie));
    }
}

void init(int nodStart) {
    for (int i=1;i<=n;++i)
        distante[i] = oo;
    distante[nodStart]=0;
    coada.push(nodStart);
    inCoada[nodStart]=true;
}

void dijkstra(int nodStart) {
    while (!coada.empty()) {
        int nodCutent = coada.top();
        coada.pop();
        for (unsigned int i=0;i<graf[nodCutent].size();++i) {
            int vecin = graf[nodCutent][i].first;
            int costMuchie = graf[nodCutent][i].second;
            if (distante[nodCutent] + costMuchie < distante[vecin]) {
                distante[vecin] = distante[nodCutent] + costMuchie;
                if (inCoada[vecin] == false) {
                    coada.push(vecin);
                    inCoada[vecin]=true;
                }
            }
        }
    }
}

void print() {
    for (int i=2;i<=n;++i)
        if (distante[i] != oo)
            g<<distante[i]<<' ';
        else g<<"0 ";
}