#include <bits/stdc++.h>
using namespace std;

constexpr int NM = 50002;
constexpr int INFINITE = 1000000000;

struct Triplet
{
    int src, dst, totalCost;

    bool operator < (const Triplet & b) const
    {
        if ( totalCost == b.totalCost )
        {
            if ( src == b.src )
                return dst > b.dst;
            return src > b.dst;
        }
        return totalCost > b.totalCost;
    }
};

struct Neighbor
{
    int nodeIndex;
    int edgeCost;
};

struct Node
{
    int distance; // Dijkstra's algorithm will fill these in
    vector< Neighbor > neighbors;
};

int ConvertLength( int length )
{
    if ( length == INFINITE ) return 0;

    return length;
}

priority_queue< Triplet > q;
Node nodes[ NM ];
bitset< NM > visited;

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

    int numNodes, numEdges, startingPoint = 1;

    fin >> numNodes >> numEdges;

    // Read input data.
    for ( int i = 1; i <= numEdges; i++ )
    {
        int node1, node2, edgeCost;
        fin >> node1 >> node2 >> edgeCost;

        nodes[node1].neighbors.push_back( { node2, edgeCost } );
    }

    // Initialize distances to infinite.
    for ( int i = 1; i <= numNodes; i++ )
    {
        nodes[i].distance = INFINITE;
    }

    nodes[startingPoint].distance = 0;

    // Initially, the priority queue will have the starting point's neighbors.
    for ( Neighbor & neighbor : nodes[startingPoint].neighbors )
    {
        q.push ( { startingPoint, neighbor.nodeIndex, neighbor.edgeCost } );
        nodes[ neighbor.nodeIndex ].distance = neighbor.edgeCost;
    }

    int numberOfNodesReached = 0;

    while (numberOfNodesReached < numNodes && !q.empty())
    {
        Triplet triplet = q.top();
        q.pop();

        if ( visited[ triplet.dst ] ) continue;

        numberOfNodesReached++;

        visited[ triplet.dst ] = true;

        for ( Neighbor & neighbor : nodes[ triplet.dst ].neighbors )
        {
            int length = nodes[ triplet.dst ].distance + neighbor.edgeCost;
            if ( !visited[ neighbor.nodeIndex ] && length < nodes[ neighbor.nodeIndex ].distance)
            {
                nodes[ neighbor.nodeIndex ].distance = length;
                q.push ( { triplet.dst, neighbor.nodeIndex, length } );
            }
        }
    }

    for ( int i = 2; i <= numNodes; i++ )
    {
        fout << ConvertLength ( nodes[ i ].distance ) << ' ';
    }

    fin.close ();
    fout.close ();

    return 0;
}