#include <iostream>
#include <fstream>
#include <queue>
#include <vector>

using namespace std;
const int maxn = 5e4+5, inf = 0x3f3f3f3f;

ifstream f("dijkstra.in");
ofstream g("dijkstra.out");

typedef struct nod
{
    int i, c;
    nod *next;
} *pNod;
pNod v[maxn];

int ans[maxn];
int n, m, i, x, y, z;
int gt[maxn];
bool done[maxn];

void add(int x, int y, int cost)
{
    pNod p = new nod;
    p -> i = y;
    p -> c = cost;
    p -> next = v[x];
    v[x] = p;
}


class pqc
{
public:
    bool operator () (const int &x, const int &y) const
    {
        return (ans[x] > ans[y]);
    }
};
priority_queue <int, vector<int>, pqc> q;

void dijkstra()
{
    q.push(1);
    done[1] = true;

    int x;
    while(!q.empty()) {
        x = q.top();
        q.pop();
        for(pNod p = v[x]; p != NULL; p = p -> next) {
            if(ans[x] + (p -> c) < ans[p -> i]) {
                ans[p -> i] = ans[x] + (p -> c);
                if(done[p -> i] == false)
                {
                    gt[p -> i] --;
                    q.push(p -> i);
                    done[p -> i] = true;
                }
            }
        }
    }
}

int main()
{
    f >> n >> m;

    for(i = 1; i <= m; i ++) {
        f >> x >> y >> z;
        add(x, y, z);
        gt[y] ++;
    }

    for(i = 2; i <= n; i ++) {
        ans[i] = inf;
    }

    dijkstra();

    for(i = 2; i <= n; i ++) {
        if(ans[i] == inf)
            g << "0 ";
        else
        g << ans[i] << ' ';
    }

    f.close();
    g.close();
    return 0;
}