#include <fstream>
#include <set>
#include <utility>
#include <vector>
#include <climits>
using namespace std;

constexpr size_t MAXN = 50010;

vector<pair<int, int>> G[MAXN];
vector<int> D;

int n;

void dijkstra(int start)
{
    D[start] = 0;

    set<pair<int, int>> Q;
    Q.insert(make_pair(0, start));

    while (!Q.empty())
    {
        pair<int, int> top = *Q.begin();
        Q.erase(Q.begin());
        int v = top.second;

        for (size_t i = 0; i < G[v].size(); ++i)
        {
            int u = G[v][i].first,
                c = G[v][i].second;
            if (D[u] > D[v] + c)
            {
                if (D[u] != INT_MAX)
                    Q.erase(Q.find( make_pair(D[u], u) ));
                D[u] = D[v] + c;
                Q.insert( make_pair(D[u], u) );
            }
        }
    }
}

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

    int m, u, v, c;
    fin >> n >> m;

    for (; m; --m)
    {
        fin >> u >> v >> c;
        G[u].push_back(make_pair(v, c));
    }

    D.resize(n+1, INT_MAX);
    dijkstra(1);

    for (size_t i = 2; i <= n; ++i)
        if (D[i] != INT_MAX)
            fout << D[i] << ' ';
        else
            fout << "0 ";
    fout << endl;

    return 0;
}