#include <bits/stdc++.h>
using namespace std;
const int nmax=5e4+5;

ifstream f ("dijkstra.in");
ofstream g("dijkstraout");

vector<pair<int,int>>adj[nmax];
int dist[nmax];
int parent[nmax];
bool viz[nmax];
int n,m;
priority_queue<pair<int,int>> heap;
void dijk (int s)
{
    dist[s]=0;
    heap.push({0,s});
    while(!heap.empty())
    {
        pair <int,int> x;
        x=heap.top();
        int nod= x.second;
        heap.pop();
        if(!viz[nod])
        {
            for(auto it: adj[nod])
            {
                if(dist[nod]+it.second<dist[it.first])
                        {dist[it.first]=dist[nod]+it.second;
                        heap.push({-dist[it.first],it.first});
                        parent[it.first]=nod;

                        }

            }
        }
        viz[nod]=1;




    }
    for(int i=2;i<=n;i++)
    if(dist[i]==INT_MAX)
        g<<0<<' ';
        else g<<dist[i]<<' ';
}

int main()
{   

   f>>n>>m;
   while(m--) 
   {    int x,y,c;
    f>>x>>y>>c;
    adj[x].push_back({y,c});

   }
   for(int i=1;i<=n;i++)
        dist[i]=INT_MAX,parent[i]=0;
    dijk(1);








  


}