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

#define m_pair pair<int, int>

using namespace std;

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

const int LIM = 50005;
const int oo = (1 << 30);

int N, M;
int D[LIM];

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

vector < m_pair > Edges[LIM];
priority_queue <int, vector < int >, cmp> Qu;

/*void Dijkstra()
{
    for(int i = 2; i <= N; i++)
        D[i] = oo;

    for(int i = 1; i < N; i++)
    {
        int currentNode = Qu.top().first;
        Qu.pop();
        for(unsigned int j = 0; j < Edges[currentNode].size(); j++)
        {
            int Neighbor    = Edges[currentNode][j].first;
            int Cost        = Edges[currentNode][j].second;
            if(D[Neighbor] > D[currentNode] + Cost)
                D[Neighbor] = D[currentNode] + Cost;
        }
    }
}*/

void Dijkstra()
{
    Qu.push(1);
    while(!Qu.empty())
    {
        int currentNode =   Qu.top();
                            Qu.pop();

        for(unsigned int i = 0; i < Edges[currentNode].size(); i++)
        {
            int Neighbor = Edges[currentNode][i].first;
            int Cost     = Edges[currentNode][i].second;
            if(D[Neighbor] > D[currentNode] + Cost)
            {
                D[Neighbor] = D[currentNode] + Cost;
                Qu.push(Neighbor);
            }
        }
    }
}

void Read()
{
    fin >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int here, there, cost;
        fin >> here >> there >> cost;
        Edges[here].push_back(make_pair(there,cost));
    }

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

    Dijkstra();

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

int main()
{
    Read();
    return 0;
}