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

const int MAX_DIST = 20000*50000;

int N, M;
int dist[50003], inqueue[50003];

// prioritize shorter distances first
// out of all neighbours
struct CompareClass
{
    bool operator ()(int x, int y)
    {
        return dist[x] > dist[y];
    }
};

priority_queue<int, vector<int>, CompareClass> pq;
vector< pair<int, int> > edges[50003];


void read()
{
    ifstream fin("dijkstra.in");
    fin >> N >> M;
    int A, B, C;

    for( int i = 1; i <= M; i++ )
    {
        fin >> A >> B >> C;
        edges[A].push_back(make_pair(B, C));
    }
    fin.close();
}

void write(){
    ofstream fout("dijkstra.out");

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

    fout.close();
}

void dijkstra(int start)
{
    int current, other, cost;

    for( int i = 1;  i <= N; ++i)
        dist[i] = MAX_DIST;

    pq.push(start);
    dist[start] = 0;
    inqueue[start] = 1;

    while( !pq.empty() )
    {
        current = pq.top(); pq.pop();
        inqueue[current] = 0;

        for( int i = 0; i < edges[current].size(); i++) // iterate through all edges
        {
            other = edges[current][i].first;
            cost = edges[current][i].second;

            if( dist[current] + cost < dist[other] ) // if it's an improvement
            {
                dist[other] = dist[current] + cost;

                // if it's not already in the queue
                if( inqueue[other] == 0 )
                {
                    pq.push(other);
                    inqueue[other] = 1;
                }
            }
        }
    }
}

int main()
{
    read();
    dijkstra(1);
    write();
    return 0;
}