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

using namespace std;

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

const int INF = 0x3f3f3f3f;

vector<pair<int, int > > Muchii[50005];
int cost[50005], n, m;
bool unvizited[50005];
int cnt = 1;
set<pair<int, int> > tc;

void GetTheCost()
{
    tc.insert({0, 1});
    while(!tc.empty())
    {
        int nod = tc.begin()->second;
        unvizited[nod] = 0;
        tc.erase(tc.begin());
        for(int i = 0; i < Muchii[nod].size(); ++i)
            if(unvizited[Muchii[nod][i].first] == 1)
            {
                int c = cost[nod] + Muchii[nod][i].second;
                if(c < cost[Muchii[nod][i].first])
                {
                    if(cost[Muchii[nod][i].first] != INF)
                        tc.erase(tc.find({cost[Muchii[nod][i].first], Muchii[nod][i].first}));
                    cost[Muchii[nod][i].first] = c;
                    tc.insert({c, Muchii[nod][i].first});
                }
            }
    }
}

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

    for(int i = 1; i <= n; ++i)
        cost[i] = INF, unvizited[i] = 1;
    for(int i = 1; i <= m; ++i)
    {
        int x, y, c;
        fin >> x >> y >> c;

        Muchii[x].push_back({y, c});
    }

    cost[1] = 0;
    GetTheCost();

    for(int i = 2; i <= n; ++i)
    {
        if(cost[i] == INF)
            cost[i] = 0;
        fout << cost[i] << ' ';
    }
    fout << '\n';
    return 0;
}