#include <fstream>
#include <cstdio>
#include <vector>
#define NMAX 50001
using namespace std;

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

struct vecin
{
    int vf, cost;
};

vector <vecin> L[NMAX];
int n, m, infinit=1000000000;
int z[NMAX],cmin[NMAX], prec[NMAX];


void citire();
void initializare(int start);
void dijkstra (int start);
void afisare(int start);

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

void citire()
{
    int i, a;
    vecin aux;
    //fin>>n>>m;
    fscanf(fin, "%d %d\n", &n, &m);
    for(i=1; i<=m; ++i)
    {
        //fin>>a>>aux.vf>>aux.cost;
        fscanf(fin, "%d %d %d\n", &a, &aux.vf, &aux.cost);
        L[a].push_back(aux);
    }
}

void dijkstra (int start)
{
    int i, j, pmin;
    initializare(start);
    for(i=1; i<n; ++i)
    {
        pmin=n+1;
        for(j=1; j<=n; ++j)
            if(cmin[i]<cmin[pmin])
            {
                pmin=i;
            }
        z[pmin]=1;
        for(j=0; j<L[pmin].size(); ++j)
            if(!z[L[pmin][j].vf] && cmin[L[pmin][j].vf]>L[pmin][j].cost+cmin[pmin])
            {
                cmin[L[pmin][j].vf]=L[pmin][j].cost+cmin[pmin];
                prec[L[pmin][j].vf]=pmin;
            }

    }
    afisare (start);
}

void initializare(int start)
{
    int i;
    cmin[n+1]=infinit;
    z[start]=1;
    for(i=1; i<=n; ++i)
        {
            cmin[i]=infinit;
            prec[i]=start;
        }
    cmin[start]=0;
    prec[start]=0;
    for(i=0; i<L[start].size(); ++i)
    {
        cmin[L[start][i].vf]=L[start][i].cost;
    }
}

void afisare(int start)
{
    int i;
    for(i=1; i<=n; ++i)
        if(i!=start)
        {
            fprintf(fout, "%d ", cmin[i]);
        }
}