// C++ Program for Dijkstra's dial implementation
#include<bits/stdc++.h>

using namespace std;

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

const int NMax = 50005;
const int oo = (1 << 30); // max int

int N,M;
vector<pair<int, list<int>::iterator> > D(NMax);
//int D[NMax];
//int viz[NMax];
//bool Inqueue[NMax];

vector< pair<int, int> > G[NMax];
//queue <int> Queue;

int Read() {
fin >> N >> M;
    int maxi = 0;
    for(int i = 1; i <= M; i++) {
        int x, y, c;
        fin >> x >> y >> c;
        if(x > maxi) {
            maxi = c;
        }
        G[x].push_back(make_pair(y,c));
    }
    return maxi;
}


// Prints shortest paths from src to all other vertices.
// W is the maximum weight of an edge
void Dijkstra_adap(int src, int maxi_cost)
{
    /* With each distance, iterator to that vertex in
       its bucket is stored so that vertex can be deleted
       in O(1) at time of updation. So
    dist[i].first = distance of ith vertex from src vertex
    dits[i].second = iterator to vertex i in bucket number */

    // Initialize all distances as infinite (INF)
    for (int i = 1; i <= N; i++)
        D[i].first = oo;

    // Create buckets B[].
    // B[i] keep vertex of distance label i
    int maxi = maxi_cost * N;
    list<int> B[maxi];

    B[0].push_back(src);
    D[src].first = 0;

    //
    int idx = 0;
    while (1)
    {
        // Go sequentially through buckets till one non-empty
        // bucket is found
        while (B[idx].size() == 0 && idx < maxi)
            idx++;

        // If all buckets are empty, we are done.
        if (idx == maxi)
            break;

        // Take top vertex from bucket and pop it
        int NodCurrent = B[idx].front();
        B[idx].pop_front();

        // Process all adjacents of extracted vertex 'u' and
        // update their distanced if required.
        for(unsigned int i = 0; i < G[NodCurrent].size(); i++) {
            int Neighbour = G[NodCurrent][i].first;
            int Cost = G[NodCurrent][i].second;

            int dnei = D[Neighbour].first;
            int dcur = D[NodCurrent].first;

            // If there is shorted path to v through u.
            if (dnei > dcur + Cost)
            {
                // If dv is not oo then it must be in B[dv]
                // bucket, so erase its entry using iterator
                // in O(1)
                if (dnei != oo)
                    B[dnei].erase(D[Neighbour].second);

                //  updating the distance
                D[Neighbour].first = dcur + Cost;
                dnei = D[Neighbour].first;

                // pushing vertex v into updated distance's bucket
                B[dnei].push_front(Neighbour);

                // storing updated iterator in dist[v].second
                D[Neighbour].second = B[dnei].begin();
            }
        }
    }

    // Print shortest distances stored in dist[]
}

void Write() {
    for(int i = 2; i <= N; i++) {
        if(D[i].first != oo)
            fout << D[i].first << " ";
        else
            fout << "0 "; // if there is no path to the node
    }
}

// Driver program to test methods of graph class
int main()
{
    // create the graph given in above fugure
    int maxi = Read();
    Dijkstra_adap(1, maxi);
    Write();
    return 0;

}