#include <iostream>
#include <queue>
#include <vector>
#include <climits>
#include <algorithm>
FILE * fin =fopen("bellmanford.in","r");
FILE * fout =fopen("bellmanford.out","w");

int n,m;
int dist[50500];
struct nod
{
  int x, d;
};
struct Comp: std::binary_function<nod,nod,bool>
{
  bool operator()(nod n1, nod n2)
  {
    return n1.d<n2.d;
  }
};
std::vector<nod> v[50500];
std::priority_queue<nod,std::vector<nod>,Comp> pq;
bool vis[50500];

int main()
{
  fscanf(fin,"%d %d",&n,&m);
  for(int i=0;i<m;i++)
  {
    int j,k,o;
    fscanf(fin,"%d %d %d",&j,&k,&o);
    v[j].push_back({k,o});
  }
  for(int i=1;i<=n;i++)
    dist[i]=INT_MAX;
  dist[1]=0;
  for(int j=0;j<m-1;j++)
  {
    for(int i=1;i<=n;i++)
      vis[i]=false;
    pq.push({1,dist[1]});
    while(!pq.empty())
    {
      nod tp = pq.top();
      pq.pop();
      if(vis[tp.x]) continue;
      std::cout<<tp.x<<"\n";
      vis[tp.x]=true;
      for(int i=0;i<v[tp.x].size();i++)
      {
        nod elem = v[tp.x][i];
        if(elem.d+tp.d<dist[elem.x])
        {
          dist[elem.x]=elem.d+tp.d;
          pq.push(elem);
        }
      }
    }
  }
  
  for(int i=1;i<=n;i++)
    vis[i]=false;
  pq.push({1,dist[1]});
  while(!pq.empty())
  {
    nod tp = pq.top();
    pq.pop();
    if(vis[tp.x]) continue;
    std::cout<<tp.x<<"\n";
    vis[tp.x]=true;
    for(int i=0;i<v[tp.x].size();i++)
    {
      nod elem = v[tp.x][i];
      if(elem.d+tp.d<dist[elem.x])
      {
        fprintf(fout,"Ciclu negativ!");
        return 0;
      }
    }
  }
  for(int i=2;i<=n;i++)
    fprintf(fout,"%d ",dist[i]);//*/
}