#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream be("dijkstra.in");
ofstream ki("dijkstra.out");

const int inf=1<<30;

vector<int> dijkstra(int start,int n,vector<vector<pair<int,int> > >&adj)
{
    vector<int> dist(n+1,inf);
    dist[start]=0;
    priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int>> >q;
    q.push({0,start});
    while(!q.empty())
    {
        auto best=q.top();
        int du=best.first;
        int u=best.second;

        q.pop();

        if(du!=dist[u])continue;

        for(auto p :adj[u])
        {
            int v=p.second;
            int edge=p.first;

            if(dist[v]>edge+du){
                dist[v]=edge+du;
                q.push({dist[v],v});
            }
        }
    }
    return dist;
}

int main()
{
    int n,m;
    be>>n>>m;
    vector<vector<pair<int,int> > >adj(n+1);
    for(int i=0;i<m;i++)
    {
        int x,y,cost;
        be>>x>>y>>cost;
        adj[x].push_back({cost,y});
    }
    auto dist=dijkstra(1,n,adj);
    for(int i=2;i<=n;i++)
    {
        if(dist[i]>=inf)
            ki<<"0"<<" ";
        else ki<<dist[i]<<" ";
    }
    ki<<endl;

    return 0;
}