#include <cstdio>
#include <algorithm>
#include <vector>
#define inf 1000000000

using namespace std;

vector< pair<int, int> > h;
vector< pair<int, int> > g[50000];
int n, m;
int viz[50000];
int dmin[50000];

bool cmp(const pair<int, int>& a, const pair<int, int>& b)
{
    return a.second > b.second;
}

int main()
{
    pair<int, int> dc;
    int i, a, b, c;
    freopen("dijkstra.in", "r", stdin);
    freopen("dijkstra.out", "w", stdout);
    scanf("%d%d", &n, &m);
    for(i = 0; i < m; i++)
    {
        scanf("%d%d%d", &a, &b, &c);
        g[a - 1].push_back(make_pair(b - 1, c));
    }
    for(i = 1; i < n; i++)
        dmin[i] = inf;
    viz[0] = 1;
    for(i = 0; i < g[0].size(); i++)
    {
        dmin[g[0][i].first] = g[0][i].second;
        h.push_back(g[0][i]);
        push_heap(h.begin(), h.end(), cmp);
    }
    while(!h.empty())
    {
        dc = h[0];
        viz[dc.first] = 1;
        pop_heap(h.begin(), h.end(), cmp);
        h.pop_back();
        for(i = 0; i < g[dc.first].size(); i++)
        {
            if(viz[g[dc.first][i].first] == 0 && dmin[g[dc.first][i].first] > dmin[dc.first] + g[dc.first][i].second)
            {
                dmin[g[dc.first][i].first] = dmin[dc.first] + g[dc.first][i].second;
                h.push_back(make_pair(g[dc.first][i].first, dmin[g[dc.first][i].first]));
                push_heap(h.begin(), h.end(), cmp);
            }
        }
    }
    for(i = 1; i < n; i++)
    {
        printf("%d ", dmin[i]);
    }
    return 0;
}