#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>

#define MAXN 50001
#define MM 250001
#define MARE (1 << 30)

using namespace std;

FILE *in, *out;

struct muchie
{
    const bool operator < ( const muchie &other )const
    {
        return cost > other.cost;
    }
    int catre, cost;
};



vector <muchie> g[MAXN];
priority_queue <muchie> coa;
int d[MAXN], n, m, viz[MAXN];

void dijkstra(int nod)
{
    for(int i = 1; i <= n; i++)
    {
        d[i] = MARE;
    }
    d[nod] = 0;
    muchie gigi;
    gigi.catre = nod;
    gigi.cost = 0;
    coa.push(gigi);

    while(!coa.empty())
    {
        muchie gigi = coa.top();
        coa.pop();
        //printf("%d %d %d\n", gigi.catre, gigi.cost, viz[gigi.catre]);
        if(viz[gigi.catre] == 0)
        {
            viz[gigi.catre] = 1;
            for(auto& i : g[gigi.catre])
            {
                if(i.cost + d[gigi.catre] < d[i.catre])
                {
                    d[i.catre] = i.cost + d[gigi.catre];
                    muchie nou;
                    nou.cost = d[i.catre];
                    nou.catre = i.catre;
                    coa.push(nou);
                }
            }
        }
    }
}


int main ()
{

    in = fopen("dijkstra.in", "r");
    out = fopen("dijkstra.out", "w");

    fscanf(in, "%d%d", &n, &m);

    int a, b, c;
    for(int i = 0; i < m; i++)
    {
        fscanf(in, "%d%d%d", &a, &b, &c);
        muchie x;
        x.catre = b;
        x.cost = c;
        g[a].push_back(x);
        //x.catre = a;
        //g[b].push_back(x);
    }
    /*
        for(int i = 1; i <= n; i++) {
            for(auto gay : g[i]) {
                printf("%d %d :: ", gay.catre, gay.cost);
            } printf("\n");
        }
    //*/


    dijkstra(1);

    for(int i = 2; i <= n; i++)
    {
        if(d[i] == MARE)
        {
            fprintf(out, "0 ");
        }
        else
        {
            fprintf(out, "%d ", d[i]);
        }
    }

    fclose(in);
    fclose(out);

    return 0;
}