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

#define dmax 50003

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];


struct comp
{
    bool operator() (int a, int b)
    {
        return minD[a] < minD[b];
    }
};

set<int, comp> heap;


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

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

    vector<edge>::iterator it;

    for(it = adj[1].begin(); it < adj[1].end(); it++)
    {
        minD[it->vertex] = it->weight;
        heap.insert(it->vertex);
    }

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

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

    for(int i=2; i<=n; i++)
        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;

}