#include <iostream>
#include <fstream>
using namespace std;

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

struct NC {
    unsigned short int nod,cost;
};

NC *p[50002];
int n,m,grad[50002],S[50002],D[50002];
const int maxim = 1000000000;

int main() {
    int i,j,k,minim=maxim,pmin;
    fin >> n >> m;
    while(fin >> i >> j >> k)
        grad[i]++;
    for(i=1;i<=n;i++)
        p[i]=new NC[grad[i]];
    fill(grad+1,grad+n+1,0);
    fin.close();

    f >> n >> m;
    while(f >> i >> j >> k) {
        grad[i]++;
        p[i][grad[i]].nod=j;
        p[i][grad[i]].cost=k;
    }

    S[1]=1;
    for(i=2;i<=n;i++)
        D[i]=maxim;
    int x;
    for(i=1;i<=grad[1];i++) {
        x=p[1][i].nod;
        D[x]=p[1][i].cost;
    }

    for(k=1;k<=n-2;k++) {
        minim=maxim;
        for(i=2;i<=n;i++)
            if(S[i]==0)
                if(D[i]<minim) {
                    minim=D[i];
                    pmin=i;
                }
        S[pmin]=1;
        /*for(int i=2;i<=n;i++) {
            cout << D[i] << ' ';
        }
        cout << "       ";
        for(int i=2;i<=n;i++) {
            cout << S[i] << ' ';
        }
        cout << endl;
        cout << pmin << ' ' << minim << "\n";*/

        for(i=1;i<=grad[pmin];i++)
        {
            x=p[pmin][i].nod;
            if(D[x]>minim+p[pmin][i].cost)
                D[x]=minim+p[pmin][i].cost;
        }
    }
    for(i=2;i<=n;i++) {
        if(D[i]==maxim)
            D[i]=0;
        fout << D[i] << ' ';
    }
    return 0;
}