#include <iostream>
#include<fstream>
#include<vector>
#define Nmax 1000001
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
struct nod_cost
{
    int nod,cost;
};
nod_cost h[50001];
vector<int>v[50001];
int n1,m,cst,x,y,n,i,j,k,parrent[50001],dist[50001],c[5000][5000];
inline int father(int nod)
{
    return nod>>1;
}
inline int left_son(int nod)
{
    return nod<<1;
}
inline int right_son(int nod)
{
    return (nod<<1)+1;
}
inline void down(int k)
{
    if(k<n)
    {
    if( (h[k].cost>h[left_son(k)].cost && left_son(k)<=n) || (right_son(k)<=n &&  h[k].cost>h[right_son(k)].cost))
    {
            if(h[left_son(k)].cost<h[right_son(k)].cost && right_son(k)<=n)
            {
                swap(h[k],h[left_son(k)]);
                down(left_son(k));
            }
            else if(right_son(k)<=n)
            {
                swap(h[k],h[right_son(k)]);
                down(right_son(k));
            }
    }
    }
}
inline void up(int k)
{
    if(k>1)
    {
        if(h[father(k)].cost>h[k].cost)
        {
            swap(h[father(k)],h[k]);
            up(father(k));
        }
    }
}
inline void cut(int k)
{
    swap(h[k],h[n]);
    n--;
    up(k);
    down(k);
}
inline int extractMin()
{
    return h[1].nod;
}
void BuildHeap()
{
    for(int i=1;i<=n;i++)
        up(i);
}
int main()
{
    f>>n>>m;
    n1=n;
    for(i=1;i<=m;i++)
    {
        f>>x>>y>>cst;
        v[x].push_back(y);
        c[x][y]=cst;
    }
    for(i=1;i<=n;i++)
    {
        h[i].nod=i;
        h[i].cost=Nmax;
    }
    h[1].cost=0;
    BuildHeap();
    dist[1]=0;
    parrent[1]=0;
    while(n>0)
    {
        i=extractMin();

        for(k=0;k<v[i].size();k++)
            if(v[i][k]<=n)
        {
            j=v[i][k];
            if(h[j].cost>h[i].cost+c[i][j])
            {
                h[j].cost=h[i].cost+c[i][j];
                parrent[j]=i;
                dist[j]=h[j].cost;
                up(j);
            }
        }
        cut(i);
    }
    for(i=2;i<=n1;i++)
        g<<dist[i]<<' ';
}