#include <fstream>
#include <cstdio>
#include <vector>
#define vfmax 50001
#define Infinit 1000000000

using namespace std;

FILE*fin=fopen("dijkstra.in", "r");
FILE*fout=fopen("dijkstra.out", "w");

void citire();
void dijkstra();
void afisare();

struct Vecin
{
    int vf;
    short int c;
};

vector <Vecin> G[vfmax];
int n, x0=1;
int cmin[vfmax], prec[vfmax];
bool Z[vfmax];

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

void citire()
{
    int m, i, x, y, c;
    Vecin aux;
    fscanf(fin, "%d%d", &n, &m);
    for(i=1; i<=n; i++)
    {
        fscanf(fin, "%d%d%d", &x, &y, &c);
        aux.vf=y;
        aux.c=c;
        G[x].push_back(aux);
    }
    Z[x0]=1;
    for(i=1; i<=n; i++)
    {
        prec[i]=x0;
        cmin[i]=Infinit;
    }
    prec[x0]=0;
    cmin[x0]=0;
    for(i=0; i<G[x0].size(); i++)
        cmin[G[x0][i].vf]=G[x0][i].c;
}

void dijkstra()
{
    int i, costmin=Infinit, j, vfmin;
    for(i=1; i<n; i++)
    {
        //determin un varf neselectat de cost costmin
        for(j=1; j<=n; j++)
            if(cmin[j]<costmin && !Z[j])
            {
                costmin=cmin[j];
                vfmin=j;
            }
        if(costmin==Infinit) return;
        Z[vfmin]=1;

        //parcurg lista de adiacenta a lui vfmin
        for(j=0; j<G[vfmin].size(); j++)
        {
            if(!Z[G[vfmin][j].vf] && cmin[G[vfmin][j].vf]>cmin[vfmin]+G[vfmin][j].c)
            {
                cmin[G[vfmin][j].vf]=cmin[vfmin]+G[vfmin][j].c;
                prec[G[vfmin][j].vf]=vfmin;
            }
        }


    }
}

void afisare()
{
    int i;
    for(i=1;i<x0;i++)
        if(cmin[i]==Infinit) fprintf(fout, "0 ");
            else fprintf(fout, "%d ", cmin[i]);
    for(i=x0+1;i<=n;i++)
        if(cmin[i]==Infinit) fprintf(fout, "0 ");
            else fprintf(fout, "%d ", cmin[i]);
    fprintf(fout, "\n");
}