#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
const int nmax = 50005;
vector <pair<int,int> > g[nmax];
int heap[nmax], dim, poz[nmax], n, m, dist[nmax];

void swap(int x, int y)
{
    int t = heap[x];
    heap[x] = heap[y];
    heap[y] = t;
}

void up(int x)
{
    int y;
    while(x>1)
    {
        y=x>>1;
        if (dist[heap[y]] > dist[heap[x]])
        {
           poz[heap[x]]=y;
           poz[heap[y]]=x;
           swap(y, x);
           x=y;
        }
        else x=1;
    }
}

void down(int x)
{
    int y;
    while(x<=dim)
    {
        y=x;
        if(x<<1 <= dim)
        {
            y=x<<1;
            if (y+1<=dim)
                if (dist[heap[y+1]] < dist[heap[y]])
                    y++;
        }
        else return;
        if (dist[heap[x]] > dist[heap[y]])
        {
            poz[heap[x]]=y;
            poz[heap[y]]=x;
            swap(x, y);
            x=y;
        }
        else return;
    }
}

void dijkstra(int start)
{
    int i, dad, son, cost;
     for(i=1; i<=n; i++)
     {
         dist[i]=(1<<29);
         poz[i]=-1;
     }
    dist[start]=0;
    heap[++dim]=start;
    poz[start]=1;
    while(dim)
    {
        dad=heap[1];
        swap(1, dim);
        poz[heap[1]]=1;
        dim--;
        down(1);
        for(i=0; i<g[dad].size(); i++)
        {
            son=g[dad][i].first;
            cost=g[dad][i].second;
            if(dist[son] > dist[dad]+cost)
            {
                dist[son]=dist[dad]+cost;
                if(poz[son]!=-1) up(poz[son]);
                else
                {
                    heap[++dim]=son;
                    poz[heap[dim]]=dim;
                    up(dim);
                }
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    int i, x, y, c;
    scanf("%d %d", &n, &m);
    for(i=1; i<=m; i++)
    {
        scanf("%d %d %d", &x, &y, &c);
        g[x].push_back(make_pair(y, c));
    }
    dijkstra(1);
    for(i=2; i<=n; i++)
        printf("%d ", dist[i]);
    fclose(stdin);
    fclose(stdout);
    return 0;
}