#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
using namespace std;

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

priority_queue<pair<int,int>> q;
vector<vector<pair<int,int>>> v;

int n,m;
int inf=1000000000;
int dist[50002];

int main()
{
    fin>>n>>m;
    int tata,fiu;
    int a,b,c;
    v.resize(n+1, vector<pair<int,int>>());
    for(int k=1;k<=m;k++)
    {
        fin>>a>>b>>c;
        v[a].push_back({b,c});
    }
    q.push({0,1});
    for(int k=2;k<=n;k++)
        dist[k]=inf;
    while(!q.empty())
    {
        pair p=q.top();
        q.pop();
        tata=p.second;
        for(vector<pair<int,int>>:: iterator k=v[tata].begin();k!=v[tata].end();k++)
        {
             fiu=k->first;
             if(dist[fiu]>dist[tata]+k->second)
             {
                 dist[fiu]=dist[tata]+k->second;
                 q.push({-dist[fiu],fiu});
             }
        }
    }
    for(int k=2;k<=n;k++)
    {
        if(dist[k]==inf)
            fout<<0<<" ";
        else
            fout<<dist[k]<<" ";
    }
    return 0;
}