#include <cstdio>
#include <cstring>
#include <algorithm>
#include <fstream>
#include <queue>
#include <vector>
#include <cmath>
#define inf 2000000000.0
#define e 0.0000000001
#define mod 104659

using namespace std;

ifstream fin ("dmin.in");
ofstream fout ("dmin.out");

struct Nod
{
    int nod;
    double cost;
    bool operator < (const Nod & e) const
    {
        if (fabs(cost - e.cost) < e)
            return 0;
        return (cost > e.cost + e);
    }
};

vector <Nod> L[1505];
int n,m,cost[1505],sol[1505];

priority_queue <Nod> q;

void Citire()
{
  int x,y;
  Nod w;
  double costt;
  fin >> n >> m;
  for (int i=1; i<=n; i++)
       cost[i] = 1;
  for (int i=1; i<=m; i++)
   {
      fin >> x >> y >> costt;
      w.nod=y;
      costt = log(costt);
      w.cost=costt;
      L[x].push_back(w);
   }
   for (int = 2; i <= n; ++ i)
        cost[i] = inf;
}

void Lee_Bellman_Ford_BFS_Dijkstra()
{
  int i,j,k,costt;
  Nod w,w1;
  w.nod=1;
  w.cost=0;
  q.push(w);
  cost[1]=0;

  while (!q.empty())
 {
   w = q.top();
   k = w.nod;
   q.pop();
   if (fabs(w.cost - cost[k]) >= e))
       continue;
   for (int j=0; j<L[k].size(); j++)
       {
            i = L[k][j].nod; costt = L[k][j].cost;

            if (cost[i] >= cost[k] + costt + e)
               {
                   cost[i] = (cost[k] + costt);
                   sol[i] = sol[k];
                   w1.nod=i;
                   w1.cost=cost[i];
                   q.push(w1);
               }
            else if (fabs(cost[i] - cost[k] - costt) <= e)
                    sol[i] = (sol[k] + sol[i]) % mod;
       }
 }
}

void Print_that()
{
 for (int i=2; i<=n; i++)
   fout << nr_drumuri[i] << " ";
 fout << "\n";
}

int main ()
{
 Citire();
 Lee_Bellman_Ford_BFS_Dijkstra();
 Print_that();
 fin.close();
 fout.close();
 return 0;
}