//heap
#include<fstream>
#include<vector>
#define infin 2000
using namespace std;
 
 
 
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int v[50002];
struct muchie
{
    int inf;
    int cost;
};
     
vector <muchie> lv[50002];
int pret[50002],aux;
int n,mm;
 
 
int poz[200000],heap[200000],ordin[200000],k=0,j=0;
void add(int cost,int nod)
{   
    poz[nod]=++j;
    ordin[j]=nod;
    heap[j]=cost;
    int j2;
    j2=j;
    while(j>1&&heap[j/2]>heap[j])
        {
            int aux;
            aux=heap[j/2];
            heap[j/2]=heap[j];
            heap[j]=aux;
            poz[ordin[j/2]]=j;
            poz[ordin[j]]=j/2;
            aux=ordin[j/2];
            ordin[j/2]=ordin[j];
            ordin[j]=aux;
            j=j/2;
        }
    j=j2;
}
 
void remove(int x)
{ 
    int u,p,aux;
    u=poz[x];
    heap[u]=heap[j];
    heap[j]=0;
    ordin[u]=ordin[j];
    poz[ordin[j]]=u;
    j--;
    while(heap[2*u]&&(heap[2*u]<heap[u]||(heap[2*u+1]&&heap[2*u+1]<heap[u])))
        {
            if(heap[2*u+1]&&heap[2*u+1]<heap[2*u])p=2*u+1;
                else p=2*u;
            aux=heap[p];
            heap[p]=heap[u];
            heap[u]=aux;
            poz[ordin[p]]=u;
            poz[ordin[u]]=p;
            aux=ordin[p];
            ordin[p]=ordin[u];
            ordin[u]=aux;
            u=p;
        }
}
 
 
int main()
{
    int i;
     
    fin>>n;
    fin>>mm;
    for(i=1;i<=mm;i++)
    {   
        int x;
        muchie y;
        fin>>x>>y.inf>>y.cost;
        lv[x].push_back(y);
    }
    add(0,1);
    pret[1]=0;
    for(i=2;i<=n;i++)
        {add(infin,i);
         pret[i]=infin;
        }
     
    int j;
     
    while(heap[1]!=infin)
    {
         int cine,cat;
         cine=ordin[1];
          
         v[cine]=1;
         cat=lv[cine].size();
         for(i=0;i<cat;i++)
         {
          
             if(!v[lv[cine][i].inf]&&pret[cine]+lv[cine][i].cost<pret[lv[cine][i].inf])
             {
                 pret[lv[cine][i].inf]=pret[cine]+lv[cine][i].cost;
                 remove(lv[cine][i].inf);
                 add(pret[lv[cine][i].inf],lv[cine][i].inf);
             }
         }
         remove(cine);
         add(infin,cine);
         
     }
      
     for(i=2;i<=n;i++)
        {if(pret[i]!=infin)fout<<pret[i]<<" ";
           else fout<<"0 ";
        }
         
          
     
    return 0;
}