#include <iostream>
#include <fstream>

using namespace std;

struct node{
  int ime;
  int predhodnik;
  int dolzina;
  int status;
};

node graf[1000];
int S[1000];
int rel[1000][1000];

// -1 e prazen sklad
int stackPtr = -1;
int nodeCount = 0;
int relCount = 0;

// stavame vrednost na skladot ako ne e poln
void push(int s)
{
  if(stackPtr > 999)
    return;
  S[++stackPtr] = s;
}

// vadime vrednost od skladot ako ne e prazen
int pop()
{
  if(stackPtr == -1)
    return -1234;
  return S[ stackPtr-- ];
}

void beri(string f)
{
  fstream dat(f.c_str(), fstream::in);
  dat >> nodeCount;
  int p, q, dol, cnt = 0;
  bool a, b;

  for(int i = 0; i < nodeCount; i++)
    graf[i].ime = i;

  while(!dat.eof())
  {
    a = true;
    b = true;
    // vcitvame vrednostite
    dat >> p >> q >> dol;

    // postavuvame relacijata
    // a->b b->a (refleksivna)
    rel[p - 1][q - 1] = 1;
    rel[q - 1][p - 1] = 1;

    cnt++;
  }

  dat.close();
  relCount = cnt;
}

void iskanje_v_globuno(int start, int cilj)
{
  for(int i = 0; i < nodeCount; i++)
  {
    graf[i].status = 0;
    graf[i].dolzina = 1000;
    graf[i].predhodnik = -1;
  }

  graf[ start ].status = 1;
  graf[ start ].dolzina = 0;
  graf[ start ].predhodnik = -1;
  push(start);

  int tmp;
  while(stackPtr != -1)
  {
    // zemame element od skladot
    tmp = pop();
    // ako e toj element elementot koj go baravme
    // prekinuvame so baranjeto
    if(graf[tmp].ime == graf[cilj].ime)
      return;
    // odime preku site elementi...
    for(int i = 0; i < nodeCount; i++)
    {
      // ... i proveruvame koj e sosed so elementot koj go dobivme od skladot
      if(rel[ graf[tmp].ime ][i] == 1)
      {
        // sekoj od sosedite gi stavame na skladot
        int sosed = i;
        if(graf[sosed].status == 0)
        {
          graf[sosed].status = 1;
          // nivnata dolzina na nastavuvame kako dolzinata na predhodnikot + 1
          graf[sosed].dolzina = graf[tmp].dolzina + 1;
          graf[sosed].predhodnik = tmp;
          // on the stack she goes
          push(sosed);
        }
        // belezime elementot kako pregledan
        graf[tmp].status = 2;
      }
    }
  }
}

void izpisi_poti(int s, int v, int c)
{
  if(s == v)
  {
    cout << "Dolzina poti do " << s + 1 << " je " << c << endl;
    cout << "Pot: " << graf[v].ime + 1 << " ";
  }
  else
  {
    if(graf[v].predhodnik == -1)
    {
      cout << "Pot ne obstaja!";
      return;
    }
    else
    {
      izpisi_poti(s, graf[v].predhodnik, c);
      cout << graf[v].ime + 1 << " ";
    }
  }
}


int main()
{
  int start, end, c = -1;

  while(c != 0)
  {
    cout << "===========================" << endl;
    cout << "1. Preberi graf iz datoteke" << endl;
    cout << "2. Pozeni iskanje iz vozlisca s do d" << endl;
    cout << "0. Konec" << endl;
    cout << "===========================" << endl;
    cout << "Izbir >>> "; cin >> c;

    switch(c)
    {
    case 1:
      beri("graf.txt");
      break;
    case 2:
      if(nodeCount == 0)
      {
        cout << "Se niste prebrali iz datoteke!" << endl;
        break;
      }

      do
      {
        cout << "Vpisite vrednost za vozlisce s >>> "; cin >> start;
      }while(start > nodeCount || start <= 0);

      do
      {
        cout << "Vpisite vrednost za vozlisce d >>> "; cin >> end;
      }while(end > nodeCount || end <= 0);

      iskanje_v_globuno(start - 1, end - 1);
      izpisi_poti(start - 1, end - 1, graf[end].dolzina);
      cout << endl;

      break;
    case 0:
      break;
    }

  }

  return 0;
}