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

using namespace std;

int n, m, dist[N], viz[N];
struct cmp
{
    bool operator()(int a, int b)
    {
        return dist[a]>dist[b];
    }
};
vector <pair<int, int> > graf[N];
vector <pair<int, int> > :: iterator it;
priority_queue <int, vector<int>, cmp> heap;

void citire()
{
    scanf("%d %d\n", &n, &m);
    int x, y, cost;
    for(int i=1;i<=m;i++)
    {
        scanf("%d %d %d\n", &x, &y, &cost);
        graf[x].push_back(make_pair(y, cost));
    }
}

void dijkstra(int x)
{
    for(it=graf[x].begin();it<graf[x].end();it++)
    {
        if(dist[it->first]>it->second+dist[x])
        {
            dist[it->first]=it->second+dist[x];
            heap.push(it->first);
        }
    }
}

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

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

    citire();
    memset(dist, inf, sizeof(dist));
    dist[1]=0;
    heap.push(1);
    while(!heap.empty())
    {
        int x=heap.top();
        heap.pop();
        dijkstra(x);
    }
    afisare();
    return 0;
}