#include <fstream>
#include <queue>
#include <vector>

using namespace std;

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

const int INF = 1e9 + 5;

struct NodeDist
{
    int dist, vertex;

    NodeDist(const int &dist, const int &vertex)
    {
        this->dist = dist;
        this->vertex = vertex;
    }

    bool operator <(const NodeDist &other) const {
        return this->dist > other.dist;
    }
};
std::priority_queue<NodeDist> pq;

int n,m;
std::vector<std::vector<NodeDist> > graph;

void ReadInput()
{
    fin >> n>> m;
    graph.resize(n + 1);

    for(int i = 0; i< m; ++i)
    {
        int u, v ,dist;
        fin >> u >> v >> dist;
        graph[u].push_back({dist,v});
    }
}
void Solve()
{
    std::vector<int> dist (n+1,INF);
    pq.push({0,1});
    while(!pq.empty())
    {
        int vertex = pq.top().vertex, vertexDistance = pq.top().dist;
        pq.pop();

        if(dist[vertex] != INF) continue;
        dist[vertex] = vertexDistance;
        for(auto& child : graph[vertex])
        {
            if(dist[child.vertex] == INF)
                pq.push({vertexDistance + child.dist, child.vertex});
        }
    }
    for(int i =2; i<= n; ++i)
        fout << (dist[i] == INF ? 0 : dist[i]) << " ";
}


int main()
{
    ReadInput();
    Solve();
    return 0;
}