#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f
#define N 50005

using namespace std;

int n,m;

vector <pair <int,int> >G[N];

priority_queue <pair<int,int> > pq;

void afisare(int d[])
{
    for(int i = 2; i <= n ; ++i)
    {
        printf("%d ",d[i]);
    }
}

void prelucrare()
{
    int d[n+5];

    for(int i = 1; i <= n; ++i)
    {
        d[i]=inf;
    }

    pq.push(make_pair(0,1));

    while(!pq.empty())
    {
        int tmp=pq.top().second;
        d[tmp]=pq.top().first;

        pq.pop();

        vector<pair<int,int> >::iterator it;

        for(it=G[tmp].begin(); it!=G[tmp].end(); ++it)
        {
            int x=d[tmp] + it->first;

            if(x < d[it->second])
            {
                pq.push(make_pair(x,it->second));
                d[it->second]=x;
            }
        }
    }
    afisare(d);
}

void citire()
{
    scanf("%d %d\n",&n,&m);

    for(int i = 0; i < m; ++i)
    {
        int a,b,c;
        scanf("%d %d %d\n",&a,&b,&c);

        G[a].push_back(make_pair(c,b));
    }
    prelucrare();
}

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

    citire();

    return 0;
}