#include<fstream>
#include<set>
#include<vector>

#define dmax 50003
#define inf 10000000

using namespace std;

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

int n, m;
int minD[dmax];


struct edge
{
    int vertex;
    int weight;
};

vector<edge> adj[dmax];



set<pair<int, int> > heap;


void dijkstra()
{
    minD[1] = 0;

    for(int i=2; i<=n; i++)
    {
        minD[i] = inf;
    }

    vector<edge>::iterator it;

    heap.insert( make_pair(0, 1));

    while(!heap.empty())
    {
        int bestN = (*heap.begin()).second;
        int bestV = (*heap.begin()).first;
        heap.erase(*heap.begin());

        for(it = adj[bestN].begin(); it < adj[bestN].end(); it++)
        {
            if(bestV + it->weight < minD[it->vertex])
            {
                minD[it->vertex] = bestV + it-> weight;
                heap.insert(make_pair(minD[it->vertex], it->vertex));
            }
        }
    }

    for(int i=2; i<=n; i++)
    {
        if(minD[i] == inf)
            out<<"0 ";
        else out<<minD[i]<<" ";
    }
}




int main()
{
    in>>n>>m;

    for(int i=1; i<=m; i++)
    {
        int a, b, w;

        in>>a>>b>>w;

        edge e;

        e.vertex = b;
        e.weight = w;
        adj[a].push_back(e);
    }
    in.close();

    dijkstra();

    out.close();
    return 0;

}