#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]=20001;
            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(nrsel!=V )
    {
        cout<<1;
        int x;
        do
        {
          x=Q.begin()->second;
          Q.erase(Q.begin());

        }while(s[x]==1);
        cout<<"Selected "<<x<<"...\n";
        s[x]=true;
        nrsel++;

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

                int v=(*pr).second;
                int c=(*pr).first;

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


                }
            }
            }


    }
    for(int i=2;i<V;i++)
    {
     fout<<d[i]<<" ";
    }
    fout<<d[v]<<" ";


}
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;
}