#include <bits/stdc++.h>
using namespace std;
long long int n,m,check,bak[2010],t1[2010],t2[2010],t3[2010],dis[2010];
int main()
{
  cin>>n>>m;
  int inf=999999999;
  for(int i=1; i<=m; i++)
  {
    cin>>t1[i]>>t2[i]>>t3[i];
  }
  for(int i=1; i<=n; i++) dis[i]=inf;
  dis[1]=0;
  for(int k=1; k<=n-1; k++)
  {
    check=0;
    for(int i=1; i<=m; i++)
    {
      if(dis[t2[i]]>dis[t1[i]]+t3[i])
      {
        dis[t2[i]]=dis[t1[i]]+t3[i];
        check=1;
      }
    }
    if(check==0) break;
  }
  int flag=0;
  for(int i=1; i<=m; i++)
  {
    if(dis[t2[i]]>dis[t1[i]]+t3[i]) flag=1;
  }
  if(flag!=1)
  {
    for(int i=1; i<=n; i++)
    {
      if(dis[i]==inf) cout<<-1<<" ";
      else cout<<dis[i]<<" ";
    }
  }
  return 0;
}