#include <fstream>
#include <vector>
#include <set>

using namespace std;

const int MAXN = 50041;
const int INF = 0x3f3f3f3f;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int n, m;
vector<pair<int, int> > graf[MAXN];
int dmin[MAXN];


void citire()
{
    fin >> n >> m;
    for (int i = 0; i < m; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        graf[x].push_back(make_pair(y, c));
    }
    for (int i = 1; i <= n; i++)
        dmin[i] = INF;
}

struct vecin
{
    int y, cost;
    bool operator<(const vecin& other) const {
        if (cost != other.cost)
            return cost < other.cost;
        return y < other.y; /// Astfel incat doua drumuri catre noduri diferite cu acelasi cost sa nu fie considerate identice
    }
};
set<vecin> q;

void dijkstra()
{
    dmin[1] = 0;
    q.insert({1, 0});

    while (!q.empty()) {
        int top = q.begin()->y;
        q.erase(q.begin());

        for (const auto& vecin : graf[top]) {
            if (dmin[vecin.first] > dmin[top] + vecin.second) {
                if (dmin[vecin.first] != INF)
                    q.erase({vecin.first, dmin[vecin.first]});
                dmin[vecin.first] = dmin[top] + vecin.second;
                q.insert({vecin.first, dmin[vecin.first]});
            }
        }
    }
}

int main() {

    citire();
    dijkstra();
    for (int i = 2; i <= n; i++)
        if (dmin[i] == INF)
            fout << "0 ";
        else
            fout << dmin[i] << " ";

    return 0;
}