#include <fstream>
#include <vector>
#include <queue>
#define DMAX 50010
#define INF 10000
using namespace std;
FILE * fin = fopen ("dijkstra.in", "r");
FILE * fout = fopen ("dijkstra.out", "w");

struct element
{
    int nod, cost;
};

struct element1
{
    int nod, cost, prec;
    friend bool operator < (element1 a, element1 b)
    {
        return a.cost>b.cost;
    };
};

void citire();
void apm();
void afisare();

int n, m;
vector <element> lista[DMAX];
priority_queue <element1> cmin;

int use[DMAX], prec[DMAX];
int cost[DMAX];

int main()
{
    citire();
    apm();
    afisare();
    
    fclose(fin);
    fclose(fout);
    return 0;
}

void citire()
{
    
    int i, a;
    element aux;
    
    fscanf(fin, "%d %d", &n,&m);
    for (i=1; i<=m; i++)
    {
        fscanf(fin, "%d %d %d", &a, &aux.nod, &aux.cost);
        lista[a].push_back(aux);
    }
}

void apm()
{
    int i, j;
    element1 minim, elem;
    bool ok;
    
    use[1]=1;
    prec[1]=0;
    
    elem.cost=elem.nod=elem.prec=INF;
    cmin.push(elem);
    
    for (i=0; i<lista[1].size(); i++)
    {
        elem.nod = lista[1][i].nod;
        elem.cost = lista[1][i].cost;
        elem.prec = 1;
        cmin.push(elem);
    }
    
    ok=1;
    while(ok)
    {
        do
        {
            minim=cmin.top();
            cmin.pop();
        }
        while (use[minim.nod] && minim.cost!=INF);
        
        if (minim.cost==INF) ok=0;
        else
        {
            use[minim.nod]=1;
            cost[minim.nod]=cost[minim.prec]+minim.cost;
            prec[minim.nod]=minim.prec;
            
            for (j=0; j<lista[minim.nod].size(); j++)
                if (!use[lista[minim.nod][j].nod])
                {
                    elem.nod = lista[minim.nod][j].nod;
                    elem.cost = lista[minim.nod][j].cost;
                    elem.prec = minim.nod;
                    cmin.push(elem);
                }
        }
    }
}

void afisare()
{
    int i;
    for (i=2; i<=n; i++)
        fprintf(fout, "%d ", cost[i]);
}