#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream is("dijkstra.in");
ofstream os("dijkstra.out");

int N, M;
int x, y, z;
int distMin[50001];
bool done[50001];

vector<pair<int,int> > G[50001];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > > P;

void Input();
void Dijkstra();

int main()
{
    Input();
    Dijkstra();

    for (int i = 2; i <= N; ++i)
    {
        if (distMin[i] != 0x3f3f3f3f)
            os << distMin[i] << " ";
        else
            os << 0 << " ";
    }

    return 0;
}

void Input()
{
    is >> N >> M;
    for (int i = 1; i <= M; ++i)
    {
        is >> x >> y >> z;
        G[x].push_back(make_pair(y,z));
    }

    for (int i = 1; i <= N; ++i)
        distMin[i] = 0x3f3f3f3f;
}

void Dijkstra()
{
    P.push(make_pair(0,1));
    distMin[1] = 0;

    while (!P.empty())
    {
        int nod = P.top().second;
        int distNow = P.top().first;
        done[nod] = true;

        for (int i = 0; i < G[nod].size(); ++i)
        {
            if (distNow + G[nod][i].second <= distMin[G[nod][i].first])
            {
                distMin[G[nod][i].first] = distNow + G[nod][i].second;
                P.push(make_pair(distMin[G[nod][i].first],G[nod][i].first));
            }
        }

        while (P.empty() && done[P.top().second] == 1)
        {
            P.pop();
        }

    }
}