#include<iostream>
#include<vector>
#include<queue>
#include<cstdio>

#define Nmax 50001
#define oo 1<<11
using namespace std;

int n, m, x, y, c;
vector< pair<int, int> > vecin[Nmax];
int dist[Nmax];
int viz[Nmax];
queue< int > Q;

void citire()
{
    freopen("dijkstra.in", "r", stdin);
    scanf("%d %d", &n, &m);
    while(m != 0)
    {
        scanf("%d %d %d", &x, &y, &c);
        vecin[x].push_back(make_pair(y,c));
        m--;
    }
}
void dijstra( int start)
{
    for(int i = 1;i <= n; i++)  dist[i] = oo;
    dist[start] = 0;
    viz[start] = 1;
    Q.push(start);

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

    while(!Q.empty())
    {
        x = Q.front();
        Q.pop();
        for(it = vecin[x].begin(); it != vecin[x].end(); it++)
        {
            if(dist[x] + (*it).second < dist[(*it).first])
            {
                dist[(*it).first] = dist[x] + (*it).second;
                Q.push((*it).first);
            }

        }
    }
}
void afisare()
{
    freopen("dijkstra.out", "w", stdout);
    for(int i = 2; i <= n; i++)
        printf("%d ", dist[i]);
}
int main()
{
    citire();
    dijstra(1);
    afisare();
    return 0;
}