#include<cstdio>
#include<queue>
#include<vector>
#define infinity 2000000000

using namespace std;
int n,m,x,y,z;
int dist[50005];
struct muchie
{
  int y,cost;
};
vector<muchie> G[50005];
muchie aux,aux2;


class cmp
{
  public:
  bool operator () (const muchie a,const muchie b)
  {
    return a.cost>b.cost;
  }
};

int main()
{
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);
  scanf("%d %d",&n,&m);
  for(int i=1;i<=m;i++)
  {
    scanf("%d%d%d",&x,&y,&z);
    aux.y=y;aux.cost=z;
    G[x].push_back(aux);
  }
  dist[1]=0;
  for(int i=2;i<=n;i++)
    dist[i]=infinity;

  priority_queue <muchie,vector<muchie>,cmp> pq;
  aux.y=1;aux.cost=0;
  pq.push(aux);
  while(!pq.empty())
  {
    aux=pq.top();
    pq.pop();
    if(aux.cost>dist[aux.y])
      continue;
    for(int i=0;i<G[aux.y].size();i++)
    {
      if(G[aux.y][i].cost+aux.cost<dist[G[aux.y][i].y])
      {
        aux2=aux;
        aux.cost=dist[G[aux.y][i].y]=G[aux.y][i].cost+aux.cost;
        aux.y=G[aux.y][i].y;
        pq.push(aux);
        aux=aux2;
      }
    }
  }
  for(int i=2;i<=n;i++)
    printf("%d ",dist[i]);
  return 0;
}