#include <cstdio>
#include <limits>
#include <vector>
#include <algorithm>
using namespace std;

const int P=50001;
unsigned int heap[P],p[P];
long long d[P];
vector <int> v[P],c[P];

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

void heap_up(int x)
{
    if(x>1&&d[heap[x]]<d[heap[x/2]])
    {
        heap_swap(x,x/2);
        heap_up(x/2);
    }
}

void heap_down(int x,int n)
{
    if(2*x<=n)
    {
        if(d[heap[x]]>d[heap[2*x]]&&d[heap[2*x]]<=d[heap[2*x+1]])
        {
            heap_swap(x,2*x);
            heap_down(2*x,n);
        }
        if(d[heap[x]]>d[heap[2*x+1]]&&d[heap[2*x+1]]<=d[heap[2*x]])
        {
            heap_swap(x,2*x+1);
            heap_down(2*x+1,n);
        }
    }
}

void dijkstra(int n)
{
    int x;
    unsigned int i;
    while(n)
    {
    x=heap[1];
    heap_swap(1,n);
    n--;
    heap_down(1,n);
    for(i=0;i<v[x].size();i++)
        if(d[v[x][i]]>=d[x]+c[x][i])
        {
            d[v[x][i]]=d[x]+c[x][i];
            heap_up(p[v[x][i]]);
        }
    }

}

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,j,a,b;
    scanf("%d%d",&n,&m);
    for(i=0;i<m;i++)
    {
        scanf("%d%d%d",&a,&b,&j);
        v[a].push_back(b);
        c[a].push_back(j);
    }
    for(i=2;i<=n;i++)
    {
        heap[i]=i;
        p[i]=i;
        d[i]=429496729100;
    }
    heap[1]=1;
    p[1]=1;
    dijkstra(n);
    for(i=2;i<=n;i++)
    {

    if(d[i]!=429496729100)
        printf("%lld ",d[i]);
    else
        printf("0 ");
    }
    return 0;
}