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

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

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

queue <int> q;

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

int main() {
    int i,j,k;
    fin >> n >> m;
    while(fin >> i >> j >> k)
        grad[i]++;
    for(i=1;i<=n;i++)
        p[i]=new NC[grad[i]+1];
    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;
    }

    for(i=2;i<=n;i++)
        D[i]=maxim;

    int x,nod;

    q.push(1);
    while(!q.empty()) {
        x=q.front(); q.pop();

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