#include <bits/stdc++.h>

#define N 50005
#define inf 1000000000
#define pp pair<int,int>
using namespace std;
int n, m, d[N];
vector<pp > G[N];

class comp {
public:
    bool operator()(pp a, pp b)
    {
        return d[a.first] > d[b.first];
    }
};

priority_queue<pp, vector<pp >, comp> Q;

void dijkstra()
{
    int i, s;
    pp p;
    for (i = 2; i <= n; i++) d[i] = inf;

    Q.push(make_pair(1, 0));
    while (!Q.empty()) {
        p = Q.top();
        Q.pop();
        s = p.first;
        if (d[s] != p.second) continue;

        for (auto x:G[s])
            if (d[s] + x.second < d[x.first]) {
                d[x.first] = d[s] + x.second;
                Q.push(make_pair(x.first, d[x.first]));
            }
    }
}

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

    int i, x, y, c;
    scanf("%i%i", &n, &m);
    for (i = 1; i <= m; i++) {
        scanf("%i%i%i", &x, &y, &c);
        G[x].push_back(make_pair(y, c));
    }

    dijkstra();
    for (i = 2; i <= n; i++)
        if (d[i] != inf)
            printf("%i ", d[i]);
        else printf("0 ");
    return 0;
}