#include <bits/stdc++.h>
#define NMAX 50009
#define MMAX 250009
#define INF 99999999
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m;
int d[NMAX];
bool uz[NMAX];
struct tip{int val;};
struct muchie { int y; int c;};

vector <muchie>v[NMAX];

inline bool operator <(tip a, tip b)
{
  return  d[a.val]>d[b.val];
}
priority_queue <tip>H;

void citire();
void djk(int start);
void afis();
int main()
{
  citire();
  djk(1);
  afis();
    return 0;
}
void citire()
{int i;
 int x,y,c;
 fin>>n>>m;
 for(i=1;i<=m;i++)
    {
     fin>>x>>y>>c;
     v[x].push_back({y,c});
    }

}
void djk(int start)
{tip act;
 muchie vec;
int i;
 for(i=0;i<NMAX;i++)
        d[i]=INF;
 uz[start]=1;
 d[1]=0;
 H.push({start});
 while(!H.empty())
        {
         act=H.top();H.pop();uz[act.val]=0;
         for( i=0;i<v[act.val].size();i++)
            {
            vec=v[act.val][i];
            if(d[vec.y]>d[act.val]+vec.c)
                {
                 d[vec.y]=d[act.val]+vec.c;
                 if(!uz[vec.y])
                    {
                     uz[vec.y]=1;
                     H.push({vec.y});
                    }
                }
            }
        }

}
void afis()
{
 int i;
 for(i=2;i<=n;i++)
         if(d[i]!=INF)
        fout<<d[i]<<" ";
         else
        fout<<0<<" ";
}