#include <stdio.h>
#include <vector>
#include <utility>
#include <queue>

using namespace std;

class Compare {
public:
    bool operator()(pair<int, int> x, pair<int, int> y) {
        return x.second > y.second;
    }
};

vector<pair<int, int>>* g;
int* len;
char* viz;

void Dijkstra() {
    priority_queue<pair<int,int>,vector<pair<int,int>>,Compare> q;
    q.push({ 1,0 });
    while (!q.empty()) {
        auto top = q.top();
        q.pop();
        viz[top.first] = 1;
        if (len[top.first] == 0)
            len[top.first] = top.second;
        for (auto e : g[top.first])
            if (!viz[e.first])
                q.push({ e.first,e.second + top.second });
    }
    
}

int main()
{
    FILE* fin, * fout;
    fin=fopen("dijkstra.in", "r");
    fout=fopen("dijkstra.out", "w");

    int n, m;
    fscanf(fin, "%i %i", &n, &m);
    g = new vector<pair<int, int>>[n + 1];
    len = new int[n + 1]{ 0 };
    viz = new char[n + 1]{ 0 };
    while (m--) {
        int x, y, val;
        fscanf(fin, "%i %i %i", &x, &y, &val);
        g[x].push_back({ y,val });
    }
    Dijkstra();
    for (int i = 2;i <= n;++i)
        fprintf(fout,"%i ", len[i]);
    

    return 0;
}