#include <fstream>
#define nMax 50001

using namespace std;

 ifstream x ("dijkstra.in");
 ofstream y ("dijkstra.out");

 struct node
 {
     int key;
     int weight;
     node *next;
 };

 struct struct2
 {
     int dist;
     bool visited;
 };

 int n;
 struct2 vertix[nMax];
 node *head[nMax],*tail[nMax];

 void add(int A, int B, int C)
 {
     node *temp;

     if(!head[A])
     {
         head[A]=new node();

         head[A]->key=B;
         head[A]->weight=C;
         head[A]->next=NULL;
         tail[A]=head[A];
     }
     else
     {
         temp=new node();

         temp->key=B;
         temp->weight=C;
         temp->next=NULL;
         tail[A]->next=temp;
         tail[A]=temp;
     }
 }

 void dijkstra(int i)
 {
     node *current;

     vertix[i].visited=true;

     int actual=i,next=0,min_dist=1000;

     int j;

     for(j=1;j<=n;j++)
        if(vertix[j].visited==true)
        {
            current=head[j];

            while(current)
            {
                if(min_dist>current->weight && vertix[current->key].visited==false)
                {
                    actual=j;
                    next=current->key;
                    min_dist=current->weight;
                }

                current=current->next;
            }
        }

     if(next)
     {
         vertix[next].dist=vertix[actual].dist+min_dist;
         dijkstra(next);
     }
 }

 void show_list(int n)
 {
     int i;
     node *current;

     for(i=1;i<=n;i++)
     {
         y<<i<<" --> ";

         current=head[i];

         while(current)
         {
             y<<current->key<<' ';

             current=current->next;
         }

         y<<'\n';
     }
     y<<'\n';
 }

int main()
{
    int i;
    int m;

    x>>n>>m;

    int A,B,C;

    for(i=1;i<=m;i++)
    {
        x>>A>>B>>C;

        add(A,B,C);
        //add(B,A,C);
    }

    //show_list(n);

    dijkstra(1);

    for(i=2;i<=n;i++)
       y<<vertix[i].dist<<' ';
    y<<'\n';

    return 0;
}