#include <stdio.h>
#include <vector>
#define Inf 1000000000

using namespace std;

int V[50001];

struct muchie
{
    int i;
    int cost;
};

vector <muchie> mc[50001];

int CT[50001];
int G[250000];
int N,M;


void actualizare(int nod,int st,int dr,int x,int cost)
{if(st==dr) G[nod]=cost;
   else
   {
    int mid;
    mid=(st+dr)/2;
    if(x<=mid)actualizare(2*nod,st,mid,x,cost);
       else actualizare(2*nod+1,mid+1,dr,x,cost);
     if(G[2*nod]<G[2*nod+1])G[nod]=G[2*nod];
        else G[nod]=G[2*nod+1];
   }
}

void do_it(int nod,int st, int dr)
{if(st==dr){
                if(st==1)G[nod]=0;
                else G[nod]=Inf;
                CT[st]=Inf;
            }
    else
    {
        int mid;
        mid=(st+dr)/2;
        do_it(nod*2,st,mid);
        do_it(nod*2+1,mid+1,dr);
        if(G[2*nod]<G[2*nod+1])G[nod]=G[2*nod];
            else G[nod]=G[2*nod+1];

    }
}

int minim(int nod, int st,int dr)
{
    if(st==dr)return st;
        else
    {
      int mid;
      mid=(st+dr)/2;
      if(G[2*nod]<G[2*nod+1])return minim(2*nod,st,mid);
          else return minim(2*nod+1,mid+1,dr);
    }
}

int main()
{
    FILE*f,*g;
    f=fopen("dijkstra.in","r");
    g=fopen("dijkstra.out","w");

    fscanf(f,"%d%d",&N,&M);
    for(int i=1;i<=M;i++)
    {
        int a;
        muchie b;
        fscanf(f,"%d",&a);
        fscanf(f,"%d%d",&b.i,&b.cost);
        mc[a].push_back(b);
    }

        do_it(1,1,N);
        while(G[1]!=Inf)
    {
         int w,q;
         w=minim(1,1,N);
         CT[w]=G[1];
         V[w]=1;
         q=mc[w].size();
         for(int i=0;i<q;i++)
         {

             if(!V[mc[w][i].i] && CT[w]+mc[w][i].cost < CT[mc[w][i].i])
             {
                 CT[mc[w][i].i]=CT[w]+mc[w][i].cost;
                 actualizare(1,1,N,mc[w][i].i,CT[mc[w][i].i]);
             }
         }
         actualizare(1,1,N,w,Inf);
     }

     for(int i=2;i<=N;i++)
        {
            if(CT[i]!=Inf) fprintf(f,"%d ",CT[i]);
                else fprintf(f,"0 ");
        }



    return 0;
}