#include<cstdio>
#include<algorithm>
#include<vector>

const int NMAX=50000;

std::vector<std::pair<int,int> > vecini[NMAX+1];

int val[NMAX+1];

int heap[NMAX+1];
int marime_heap;

int tata(int nod)
{
 return nod/2;
}

int fiu_st(int nod)
{
 return 2*nod;
}

int fiu_dr(int nod)
{
 return 2*nod+1;
}

void Swap(int x,int y)
{
 std::swap(heap[x],heap[y]);
}

void Up(int nod)
{
 while(nod>1 && val[heap[nod]]<val[heap[tata(nod)]])
       {
        Swap(nod,tata(nod));
        nod=tata(nod);
       }
}

void Down(int nod)
{
 while(nod<marime_heap)
       {
        int best=nod;
        if(fiu_st(nod)<=marime_heap && val[heap[fiu_st(nod)]]<val[heap[best]])
           best=fiu_st(nod);
        if(fiu_dr(nod)<=marime_heap && val[heap[fiu_dr(nod)]]<val[heap[best]])
           best=fiu_dr(nod);
        if(best==nod)
           return;
        Swap(nod,best);
        nod=best;
       }
}

void Add(int nod)
{
 heap[++marime_heap]=nod;
 Up(marime_heap);
}

void Remove(int nod)
{
 Swap(nod,marime_heap);
 marime_heap--;
 Down(nod);
 Up(nod);
}

int Get_min()
{
 return heap[1];
}

void Dijkstra(int nod)
{
 val[nod]=0;
 Add(nod);
 while(marime_heap>0)
       {
        nod=Get_min();
        Remove(1);
        for(std::vector<std::pair<int,int> >::iterator i=vecini[nod].begin();i!=vecini[nod].end();i++)
            {
             //int x,cost;
             //x=i->first,cost=i->second;

             if(val[i->first]!=0)
                continue;
             val[i->first]=val[nod]+i->second;
             Add(i->first);
            }
       }
}

void Print_val(int n,FILE *where)
{
 for(int i=2;i<=n;i++)
     fprintf(where,"%d ",val[i]);
}

int main()
{
 FILE *in=fopen("dijkstra.in","r");
 int n,m;
 fscanf(in,"%d %d ",&n,&m);
 for(int i=1;i<=m;i++)
     {
      int x,y,cost;
      fscanf(in,"%d %d %d ",&x,&y,&cost);
      vecini[x].push_back(std::make_pair(y,cost));
     }
 fclose(in);
 FILE *out=fopen("dijkstra.out","w");
 Dijkstra(1);
 Print_val(n,out);
 fclose(out);
 return 0;
}