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

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

#define inf 1900000000

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

int n,m,grad[50002],D[50002],S[50002];
NC *p[50002];

//nod start = 1

int main() {
    int i,j,k,nodcrt,minim,indice,x;

    f >> n >> m;
    while(f >> i >> j >> k)
        grad[i]++;
    f.close();

    for(i=1;i<=n;i++)
        {p[i]=new NC[grad[i]+2];grad[i]=0;}

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

    for(i=1;i<=n;i++)
        D[i]=inf;

    nodcrt=1; D[1]=0; S[1]=1;
    for(i=1;i<=grad[1];i++) {
        D[p[1][i].nod]=p[1][i].cost;
    }

    for(k=1;k<=n-2;k++) {
        minim=inf;
        for(i=2;i<=n;i++)
            if(S[i]==0 && D[i]<minim) {
                minim=D[i]; indice=i;
            }
        nodcrt=indice;
        S[nodcrt]=1;

        for(i=1;i<=grad[nodcrt];i++) {
            x=p[nodcrt][i].nod;
            if(D[nodcrt]+p[nodcrt][i].cost<D[x])
                D[x]=D[nodcrt]+p[nodcrt][i].cost;
        }
    }

    for(i=2;i<=n;i++)
        fout << D[i] << ' ';
    return 0;
}