#include<queue>
#include<cstdio>
#include<vector>
using namespace std;
int cost[50001];
class Compare
{
  public:
    bool operator()(const int &x, const int &y)
      {
        return cost[x]>cost[y];
      }
};
priority_queue <int, vector <int>, Compare> Heap;

vector <pair <int,int> > g[50001];

int main()
{
  freopen("dijkstra.in","r",stdin);
  freopen("dijkstra.out","w",stdout);
  int n,m,i,x,y,c;
  scanf("%d%d",&n,&m);
  for(i=1;i<=m;i++)
  {
    scanf("%d%d%d",&x,&y,&c);
    g[x].push_back(make_pair(y,c));
  }
  for(i=1;i<=n;i++)
    cost[i]=1<<31-1;
  Heap.push(1);
  cost[1]=0;
  while(!Heap.empty())
  {
    int nod=Heap.top();
    Heap.pop();
    for(i=0;i<g[nod].size();i++)
    {
      int vec=g[nod][i].first;
      int muc=g[nod][i].second;
      if(cost[nod]+muc<cost[vec])
      {
        cost[vec]=cost[nod]+muc;
        Heap.push(vec);
      }
    }
  }
  for(i=2;i<=n;i++)
    printf("%d ",cost[i]);
  return 0;
}