#include <iostream>
#include <fstream>
#include <vector>
#include <queue>

using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int N,M;
int D[50001],S[50001];
vector <pair<int,int> > G[50001];

struct compare
{
    bool operator()(int a,int b)
    {
        return D[a] > D[b];
    }
};

priority_queue<int , vector<int>, compare> Q;

int INF = 1<<30;

void Read()
{
    fin>>N>>M;

    for(int i=1;i<=M;i++)
    {
        int x,y,c;
        fin>>x>>y>>c;

        G[x].push_back(make_pair(y,c));
    }
}

void Dijkstra()
{
    for(int i=1;i<=N;i++)
        D[i] = INF;
    D[1] = 0;
    S[1] = 1;
    Q.push(1);

    while(!Q.empty())
    {
        int Nod = Q.top();
        Q.pop();
        S[Nod] = 1;

        for(int i=0;i<(int)G[Nod].size();i++)
        {
            int vecin = G[Nod][i].first;
            int cost = G[Nod][i].second;

            if (D[vecin] > D[Nod] + cost)
            {
                D[vecin] = D[Nod] + cost;

                if (!S[vecin])
                {
                    Q.push(vecin);
                    S[vecin] = 1;
                }
            }
        }
    }
}

int main()
{
    Read();

    Dijkstra();

    for(int i=2;i<=N;i++)
    {
        if (D[i] == INF)
            fout<<0<<' ';
        else
            fout<<D[i]<<' ';
    }

    return 0;
}