#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <climits>
int main()
{
    std::ifstream fin;
    fin.open("dijkstra.in");
    std::ofstream fout;
    fout.open("dijkstra.out");
    int verticesCount, arcsCount;
    fin>>verticesCount>>arcsCount;
    std::vector< std::pair<int,int> > adjList[50001];
    std::priority_queue< std::pair<int,int> > q;
    int arcFrom, arcTo, cost;
    for(int i=1;i<=arcsCount;i++)
    {
        fin>>arcFrom>>arcTo>>cost;
        adjList[arcFrom].push_back(std::make_pair(cost,arcTo) );
    }
    int vis[50001] = {0};
    int costList[50001];
    for (int i=1; i <= verticesCount; i++)
    {
        costList[i] = INT_MAX;
    }
    
    q.push(std::make_pair(0,1));
    costList[1] = 0;
    
    while (!q.empty()) {
        std::pair<int,int> curentVertex;
        curentVertex = q.top();
        q.pop();
        if(!vis[curentVertex.second])
        {
            vis[curentVertex.second] = 1;
            for (auto const& vertex: adjList[curentVertex.second])
            {
                int curentCost = curentVertex.first + vertex.first;
                if( costList[vertex.second] > curentCost)
                {
                    costList[vertex.second] = curentCost;
                    q.push(vertex);
                }
            }
        }
    }
    for (int i=2;i<=verticesCount;i++)
        if(costList[i] != INT_MAX) fout<< costList[i] << " ";
        else fout<<"-1 ";
    
    return 0;
}