#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
struct arce{int a;
            int b;
           int c;}arc[250001];

int n,m,dist[50001];

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
scanf("%d%d",&n,&m);
int i,pp=0;
for(i=1;i<=m;i++){
    scanf("%d%d%d",&arc[i].a,&arc[i].b,&arc[i].c);
    if(arc[i].a==1)
       dist[arc[i].b]=arc[i].c;
}
for(i=2;i<=n;i++)
        if(dist[i]==0)
            dist[i]=2000000001;

while(!pp)
  {pp=1;
   for(i=1;i<=m;i++)
      if(dist[arc[i].a] + arc[i].c < dist[arc[i].b]){
          dist[arc[i].b]=dist[arc[i].a] + arc[i].c;
          pp=0;
      }
  }
  for(i=2;i<=n;i++){
     if(dist[i]==2000000001)
        printf("0 ");
     else
       printf("%d ",dist[i]);
  }

    return 0;
}