#include <iostream>
#include <vector>
#include <list>
#include <stdio.h>
#include <queue>
#include <bitset>
#define NMAX 50005
#define DMAX 0xfffffff

using namespace std;

void read(),solve(),write();

typedef pair<unsigned int,unsigned int> pereche;
typedef list<pereche> lista;

struct cmp
{
    bool operator()(const pereche &a, const pereche &b)
    const
    {
        return a.second>b.second;
    }
};

lista G[NMAX];
vector<unsigned int> dist(NMAX,DMAX);
priority_queue<pereche,vector<pereche>,cmp>coada;
bitset<NMAX> verificat(0);

int N,M;

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);

    read();
    solve();
    write();

    return 0;
}

void write()
{
    for(int i=2;i<=N;i++)
        cout<<nounitbuf<<(dist[i]!=DMAX?dist[i]:0)<<" ";
}

void solve()
{
    dist[1]=0;
    coada.push(pereche(1,0));

    while(!coada.empty())
    {
        pereche aux=coada.top();
        unsigned int nod=aux.first, cost=aux.second;
        coada.pop();
        if(!verificat[nod])
        {
            for(lista::iterator it=G[nod].begin();it!=G[nod].end();it++)
                if(dist[(*it).first]>cost+(*it).second)
                {
                    dist[(*it).first]=cost+(*it).second;
                    coada.push(pereche((*it).first,dist[(*it).first]));
                }
            verificat[nod]=true;
        }
    }
}

void read()
{
    scanf("%d %d", &N, &M);
    for(int i=0;i<M;i++)
    {
        int s,d,c;
        scanf("%d %d %d", &s, &d, &c);
        G[s].push_back(pereche(d,c));
    }
}