#include <iostream>
#include <fstream>
#include <list>
#include <vector>
#include <set>
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


class Graph
{
    int V;
    list<pair <int, int> > *adj;
    int d[50000], t[50000];

public:
    Graph(int v);
   void  addNode(int u, int v, int c);
    void Dijkstra(int st);
};
Graph::Graph(int v)
{
    V=v;
    adj=new list<pair <int, int> >[V+1];
    for(int i=1;i<=V;i++)
        {
            d[i]=999999;
            t[i]=0;
        }
}
void Graph::addNode(int u, int v,int c)
{
   // adj[v].push_back({c,u});
    adj[u].push_back({c,v});
}
void Graph::Dijkstra(int st)
{
    d[st]=0;
    set< pair<int, int> > Q;//priority queue
    /*for(int i=1;i<=V;i++)
        Q.insert({d[i],i});*/
    Q.insert({d[st],st});

    vector <bool> s(V+1);
    /*for(int i=0;i<=V;i++)
        s[i]=false;*/
    //int nrsel=0;
   // bool ok=false;
    while(!Q.empty() )
    {
        int x;
        x=Q.begin()->second;
        Q.erase(Q.begin());

        //cout<<"Selected "<<x<<"...\n";
        //s[x]=true;

        for(std::list< pair<int, int> >::iterator pr=adj[x].begin(); pr!=adj[x].end();pr++)
            {
               // cout<<(*pr).second<<"\n";
                int v=(*pr).second;
                int c=(*pr).first;

                if(d[v]>d[x]+c)
                {
                   // cout<<"inserted "<<v<<"\n";
                   Q.erase({d[v],v});
                    d[v]=d[x]+c;
                    t[v]=x;
                    Q.insert({d[v],v});


                }
            }



    }
    for(int i=2;i<=V;i++)
    {
        if(d[i]==20001)
            d[i]=0;
     fout<<d[i]<<" ";
    }
    fout<<"\n";


}
int main()
{
    int n, m;
    fin>>n>>m;
    Graph G(n);

    for(int i=0;i<m;i++)
    {
      int x, y, p;
      fin>>x>>y>>p;
      G.addNode(x,y,p);
    }
    //cin>>st>>fin;
    G.Dijkstra(1);
    return 0;
}