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

#define max_size 50001
#define max_value 20005

using namespace std;

int n, m, a, b, c, d[max_size];
bool viz[max_size];
vector<pair<int, int>> v[max_size];
priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
int main()
{
    freopen("dijkstra.in", "r");
    freopen("dijkstra.out", "w");
    scanf("%d%d", n, m);
    for(int i = 1; i <= m; i++)
    {
        scanf("%d%d%d", a, b, c);
        v[a].push_back(make_pair(b, c));
    }
    for(int i = 2; i <= n; i++)
        d[i] = max_value;
    d[1] = 0;
    q.push(make_pair(1, 0));
    while(!q.empty())
    {
        a = q.top().first;
        q.pop();
        if(viz[a])continue;
        viz[a] = 1;
        for(auto it : v[a])
        {
            if(d[a] + it.second < d[it.first])
            {
                d[it.first] = d[a] + it.second;
                q.push(make_pair(it.first, d[it.first]));
            }
        }
    }
    for(int i = 2; i <= n; i++)
        pritnf("%d ", d[i] == max_value?0:d[i]);
    return 0;
}