#include <iostream>
#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
#define INF 20005

using namespace std;

int n, m, viz[50005], t[50005], dist[50005];
vector <pair<int, int> > g[50005];
vector <pair<int, int> >::iterator it;
priority_queue <pair <int, int> > q;

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


void citire()
{
    scanf("%d %d", &n, &m);
    int x, y, d;
    for(int i=1; i<=m; ++i)
    {
        scanf("%d %d %d", &x, &y, &d);
        g[x].push_back(make_pair(y, d));
    }
    dist[1]=0;
    for(int i=2; i<=n; ++i)
        dist[i]=INF;
}

void rezolvare()
{
    q.push(make_pair(0, 1));
    while(!q.empty())
    {
        int k=q.top().second;
        int distantaK=(-1)*q.top().first;
        q.pop();
        viz[k]=1;
        for(it=g[k].begin(); it!=g[k].end(); ++it)
        {
            if(dist[it->first]>distantaK+it->second && viz[it->first]==0)
            {
                dist[it->first]=distantaK+it->second;
                t[it->first]=k;
                q.push(make_pair((-1)*dist[it->first], it->first));
            }
        }
    }
}

int main()
{
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    citire();
    rezolvare();
    afisare();
    return 0;
}