#include <fstream>
#include <vector>
#define NMAX 50004
#define INF 1000000004

using namespace std;

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

int n, m, p;

struct varf {
    int x;
    int cost;
};

vector <varf> G[NMAX];
bool uz[NMAX];
int cmin[NMAX];
int H[NMAX]; /// aici retin vf dupa cmin
int nr;
int poz[NMAX];
///poz[x] = 0, daca nu e in heap
///pozitia

void citire();
void dijkstra();
void afisare();
int extrage_min(int H[], int &n);
void inserare(int H[], int &n, int x);
void combinare(int H[], int n, int poz);
void upgrade(int H[], int n, int poz);

int main()
{
 citire();
 dijkstra();
 afisare();
 return 0;
}

void citire() {
    int x;
    varf vf;
    fin>>n>>m;
    for (int i=1; i<=n; i++) {
        fin>>x>>vf.x>>vf.cost;
        G[x].push_back(vf);
    } p = 1;
    H[1] = p;
    nr = 1; poz[p] = 1;
}

void dijkstra() {
    varf vfmin;
    int x;
    for (int i=1; i<=n; i++) cmin[i] = INF;
    cmin[p] = 0;
    for (int i=1; i<=n; i++) {
        vfmin.x = extrage_min(H, nr);
        vfmin.cost = cmin[vfmin.x];
        if (vfmin.cost == INF) return;
        uz[vfmin.x] = 1;
        for (int j=0; j<G[vfmin.x].size(); j++) {
            x = G[vfmin.x][j].x;
            if (!uz[x])
                if ((vfmin.cost + G[vfmin.x][j].cost) < cmin[x]) {
                    cmin[x] = vfmin.cost + G[vfmin.x][j].cost;
                    ///upgrade, promovez varful in Heap pana ahunge la pozitia corecta
                    if (poz[x]!=0) upgrade(H, nr, poz[x]);
                        else inserare(H, nr, x);

                }

        }
    }
}


void afisare() {
    for (int i=2; i<=n; i++)
        if (cmin[i] == INF) fout<<"0"<<' ';
            else fout<<cmin[i]<<' ';
    fout<<'\n';

}

void inserare(int H[], int &n, int x) {
    int fiu, tata;
    fiu = n+1; tata=fiu/2;
    while (tata && cmin[H[tata]] > cmin[x]) {
        H[fiu] = H[tata]; poz[H[tata]] = fiu;
        fiu = tata;
        tata = fiu/2;
    }
    H[fiu] = x; n++; poz[x] = fiu;
}

void combinare(int H[], int n, int ppoz) {///combina H[poz] cu heap-urile (corecte!) pe poz 2poz si 2poz+1
    int x = H[ppoz], fiu, tata;
    tata = ppoz;
    fiu = 2*tata;
    while (fiu<=n) {
        if (fiu+1<=n && cmin[H[fiu+1]] < cmin[H[fiu]]) fiu++;
        if (cmin[H[fiu]] >= cmin[x]) break;
        H[tata] = H[fiu]; poz[H[fiu]] = tata;
        tata = fiu;
        fiu = 2*tata;
    }
    H[tata] = x; poz[x] = tata;
}

int extrage_min(int H[], int &n) {
    int minim = H[1];
    H[1] = H[n]; n--;
    combinare(H, n, 1);
    return minim;
}

void upgrade(int H[], int n, int ppoz) {
    int fiu = ppoz, tata = fiu/2, aux;
    while (tata) {
        if (cmin[H[fiu]] >= cmin[H[tata]]) break;
        aux = H[fiu]; H[fiu] = H[tata]; H[tata] = aux;
        aux = poz[H[fiu]]; poz[H[fiu]] = poz[H[tata]]; poz[H[tata]] = aux;
        fiu = tata;
        tata = fiu/2;
    }

}