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

using namespace std;

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

int INF = 2000000000;

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));
    }

    for(int i=1;i<=N;i++)
        D[i] = INF;
    D[1] = 0;
}

void DIJKSTRA()
{
    for(int p=1;p<=N;p++)
    {
        int Min = INF,Nod=0;

        for(int i=1;i<=N;i++)
        {
            if (D[i] < Min && S[i] == 0)
            {
                Min = D[i];
                Nod = i;
            }
        }

        S[Nod] = 1;

        for(int i=0;i<(int)G[Nod].size();i++)
        {
            int v = G[Nod][i].first;
            //if (S[v] == 0)
            D[v] = min(D[v], D[Nod] + G[Nod][i].second);
        }

        /**for(int i=1;i<=N;i++)
        {
            if (A[Nod][i] != INF && Nod != i)
            {
                D[i] = min(D[i], D[Nod] + A[Nod][i]);
            }
        }*/
    }
}

int main()
{
    Read();

    DIJKSTRA();

    for(int i=2;i<=N;i++)
        fout<<D[i]<<' ';

	return 0;
}