#include <bits/stdc++.h>
using namespace std;
#define N 50010
#define nmax 1000000010

vector<int>v[N], d[N];

int arb[N], pos[N], nr[N],n,m, k, dist[N], a,b,c;
bool viz[N];
void heap_push(int x)
{
    if(x==1 || arb[x]>arb[x/2]) return;
    else
    {
        swap(arb[x],arb[x/2]);
        swap(pos[nr[x]],pos[nr[x/2]]);
        swap(nr[x],nr[x/2]);
        heap_push(x/2);
    }
}
void heap_equilibrate(int x)
{
    if(x*2>n) return;
    if(arb[x]>arb[x*2] && (arb[x*2]<arb[x*2+1] || x*2+1>n))
    {
        swap(arb[x],arb[x*2]);
        swap(pos[nr[x]],pos[nr[x*2]]);
        swap(nr[x],nr[x*2]);
        heap_equilibrate(x*2);
        return;
    }
    if(x*2+1<=n && arb[x]> arb[x*2+1] )
    {
        swap(arb[x],arb[x*2+1]);
        swap(pos[nr[x]],pos[nr[x*2+1]]);
        swap(nr[x],nr[x*2+1]);
        heap_equilibrate(x*2+1);
        return;
    }

}

void dijkstra(int x)
{
    k++;
    viz[x] = 1;
    arb[pos[x]] = nmax;
    heap_equilibrate(pos[x]);
    for(int i=0;i<v[x].size();i++)
    {
        if(!viz[v[x][i]])
        {

            if(dist[x]+d[x][i] < dist[v[x][i]])
            {
                dist[v[x][i]] = dist[x]+d[x][i];
                arb[pos[v[x][i]]] = dist[v[x][i]];
                heap_push(pos[v[x][i]]);
            }
        }


    }
    if(k<n) dijkstra(nr[1]);
}

int main()
{
    ifstream cin("dijkstra.in");
    ofstream cout("dijkstra.out");
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        v[a].push_back(b);
        v[b].push_back(a);
        d[a].push_back(c);
        d[b].push_back(c);
    }
    for(int i=2;i<=n;i++)
        dist[i] = nmax;
    pos[1] = 1;
    nr[1] = 1;
    for(int i=2;i<=n;i++)
    {
        arb[i] = dist[i];
        pos[i] = i;
        nr[i] = i;
    }

    dijkstra(1);

    for(int i=2;i<=n;i++)
        cout<<dist[i]<<' ';

    return 0;
}