/******************************************************************************

                              Online C++ Compiler.
               Code, Compile, Run and Debug C++ program online.
Write your code in this editor and press "Run" button to compile and execute it.

*******************************************************************************/

#include <bits/stdc++.h>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> q;
int dist[50001],l[50001];
vector<vector<pair<int,int>>> graf(50001);
int main()
{
    int n,i,j,m,x,y,c;
    fin>>n>>m;
    for(i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        l[x]++;
        graf[x].push_back({y,c});
    }
    for(i=2;i<=n;i++)
    {
        dist[i]=100000000;
    }
    q.push({0,1});
    while(!q.empty())
    {
        int d=q.top().first;
        int u=q.top().second;
        q.pop();
        if(d>dist[u]) continue;
        for(i=0;i<l[u];i++)
        {
            if(dist[u]+graf[u][i].second<dist[graf[u][i].first])
            {
                dist[graf[u][i].first]=dist[u]+graf[u][i].second;
                q.push({dist[graf[u][i].first],graf[u][i].first});
            }
        }
    }
    for(i=2;i<=n;i++)
    {
        if(dist[i]!=100000000)
        {
            fout<<dist[i]<<" ";
        }
        else fout<<0<<" ";
    }
    return 0;
}