/**
 * Format vstupu:
 * Na zaciatku sa zada pocet vrcholov a hran, oddelenymi medzerami.
 * Potom nasleduje postupne N popisov vrcholov, spolu s ich hranami.
 * Popis vrcholu sa zada ako:
 * "v C S" - C je cislo vrcholu, S je stupen.
 * Nasleduje S (stupen) popisov hran.
 * Popis hrany veducej z/do vrcholu je nasledovny:
 * "S C V H"
 * S je smer hrany - bud pismeno 'i' (in) alebo 'o' (out)
 * C je cislo hrany
 * V je druhy koniec hrany (jeden koniec je v sucasnom vrchole)
 * H je hodnota hrany
 *
 * Vsetky cisla a pismena su oddelene lubovolnym mnozstvom whitespace znakov,
 * tj. medzier, novych riadok alebo tabulatorov.
 *
 * Vsetky vrcholy a hrany su indexovane od 0.
 */


#include <stdio.h>
#include <stdlib.h>

#define DELKA_RADKU 100
#define MAXINT 10000

enum Smer {IN, OUT};
enum Bool {false, true};

  // struktura urcena na nacitanie hran grafu
typedef struct {
  enum Smer typ;
  int cislo; // cislo hrany
} PovodnaHrana;

  // struktura urcena na nacitanie vrcholov grafu
typedef struct {
  int pocet_hran;
  PovodnaHrana* hrany;
} Vrchol;

struct S;

  // struktura pouzivana pri hladani ciest v "grafe hran"
typedef struct H {
  int cislo;
  int hodnota;
  enum Bool spracovana; // ci bola hrana spracovana
  enum Bool prejdena_vpred; // zarazka kvoli zacykleniu
  struct H* nasledovnik; // ukazatel na nasledovnika
  struct S* predchodca; // spojak ukazatelov na predchodcov
  struct S* posledny; // ukazatel na koniec spojaku predchodcov
  int zaciatocny_vrchol;
  int koncovy_vrchol;
} Hrana;

  // prvok spojoveho zoznamu hran
typedef struct S {
  Hrana* hrana;
  struct S * previous;
  struct S * next;
} Spojak;

int main (int argc, char** argv) {

  int N; // pocet vrcholov
  int M; // pocet hran

  scanf (" %d %d ", &N, &M);

  char radek_vstupu [DELKA_RADKU];

  Vrchol* vrcholy = (Vrchol*) malloc (N * sizeof(Vrchol));
  Hrana* hrany = (Hrana*) malloc (M * sizeof (Hrana));

    /* nastavim hodnoty v poli hran */
  for (int i=0; i<M; i++) {
    hrany[i].cislo = i;
    hrany[i].spracovana = false;
    hrany[i].prejdena_vpred = false;
    hrany[i].nasledovnik = NULL;
    hrany[i].predchodca = NULL;
    hrany[i].posledny = NULL;
  }

    /* nacitanie vstupu */
  for (int i=0; i<N; i++) {
    int pocet_hran;
    int cislo_v; // cislo vrcholu
    scanf (" v %d %d ", &cislo_v, &pocet_hran);
    vrcholy[cislo_v].pocet_hran = pocet_hran;
    vrcholy[cislo_v].hrany = (PovodnaHrana*) malloc (pocet_hran * sizeof (PovodnaHrana));
    for (int j=0; j<pocet_hran; j++) {
      char t;
      int cislo_h; // cislo hrany
      int v;
      int cena;
      scanf (" %c %d %d %d ", &t, &cislo_h, &v, &cena);
      vrcholy[cislo_v].hrany[j].cislo = cislo_h;
      hrany[cislo_h].hodnota = cena;
      switch (t) {
        case 'o':
          vrcholy[cislo_v].hrany[j].typ = OUT;
          hrany[cislo_h].koncovy_vrchol = v;
          break;
        case 'i':
          vrcholy[cislo_v].hrany[j].typ = IN;
          hrany[cislo_h].zaciatocny_vrchol = v;
          break;
      }
    }
  }

    /* doplnim zoznam hran o predchodcov a nasledovnikov */

  for (int i=0; i<N; i++) {
    Hrana* hrana_out = NULL; // nasledovnik
      // index poslednej hrany veducej von z vrcholu
    int index = -1;
      // najdem hranu veducu von z vrcholu
    for (int j=vrcholy[i].pocet_hran-1; j>=0; j--) {
      if (vrcholy[i].hrany[j].typ == OUT) {
        index = j;
        break;
      }
    }
    if (index == -1) { // neexistuje ziadna hrana vychadzajuca z vrcholu
      for (int j=vrcholy[i].pocet_hran-1; j>=0; j--) {
        hrany[vrcholy[i].hrany[j].cislo].nasledovnik = NULL;
      }
    } else {
      hrana_out = &hrany[vrcholy[i].hrany[index].cislo];
      for (int j=index-1; j>=0; j--) {
        switch (vrcholy[i].hrany[j].typ) {
          case IN: {
            hrany[vrcholy[i].hrany[j].cislo].nasledovnik = hrana_out;
              // pridam tuto hranu ako predchodcu hrany veducej von z vrcholu
            Spojak* predchodca = (Spojak*) malloc (sizeof (Spojak));
            predchodca->hrana = &hrany[vrcholy[i].hrany[j].cislo];
            predchodca->next = NULL;
            if (hrana_out->posledny != NULL) {
              hrana_out->posledny->next = predchodca;
              predchodca->previous = hrana_out->posledny;
            } else {
              predchodca->previous = NULL;
              hrana_out->predchodca = predchodca;
            }
            hrana_out->posledny = predchodca;
            break;
          }
          case OUT: {
            hrana_out = &hrany[vrcholy[i].hrany[j].cislo];
          }
        }
      }
        /* este doplnim nasledovnikov vstupnych hran,
         ktore som preskocila na zaciatku */
        /* to uz budu vsetko len vstupne hrany,
         lebo som zacala poslednou vystupnou hranou a postupujem odzadu */
      for (int j=vrcholy[i].pocet_hran-1; j>index; j--) {
        hrany[vrcholy[i].hrany[j].cislo].nasledovnik = hrana_out;
        Spojak* predchodca = (Spojak*) malloc (sizeof (Spojak));
        predchodca->hrana = &hrany[vrcholy[i].hrany[j].cislo];
        predchodca->next = NULL;
        if (hrana_out->posledny != NULL) {
          hrana_out->posledny->next = predchodca;
          predchodca->previous = hrana_out->posledny;
        } else {
          predchodca->previous = NULL;
          hrana_out->predchodca = predchodca;
        }
        hrana_out->posledny = predchodca;
      }
    }
  }

    /* hladanie ciest */
  int najlepsia_cena = MAXINT;
  Hrana* najlepsia_cesta = NULL; // zaciatocna hrana najlepsej cesty
  int* navstivene_vrcholy = (int*) malloc (N * sizeof (int));

  int zaciatok_komponenty = 0;

  while (zaciatok_komponenty < M) {
    for (int i=0; i<N; i++) {
      navstivene_vrcholy[i] = 0;
    }

    int pocet_roznych = 0;
    int cena = 0;

    Spojak* zaciatok = NULL;
    Spojak* koniec = NULL;

      /* vytvorim spojak s jednou zaciatocnou hranou */
    zaciatok = (Spojak*) malloc (sizeof (Spojak));
    zaciatok->hrana = &hrany[zaciatok_komponenty];
    zaciatok->next = NULL;
    zaciatok->previous = NULL;
    koniec = zaciatok;

      /* pridame zaciatocny a koncovy vrchol hrany do zoznamu
        navstivenych vrcholov*/
      /* tieto vrcholy su urcite rozne a este nenavstivene */
    navstivene_vrcholy[zaciatok->hrana->zaciatocny_vrchol]++;
    pocet_roznych++;
    navstivene_vrcholy[zaciatok->hrana->koncovy_vrchol]++;
    pocet_roznych++;

    Spojak* clanok = NULL;

    cena = hrany[zaciatok_komponenty].hodnota;
    hrany[zaciatok_komponenty].spracovana = true;

    int dlzka = 1; // dlzka cesty

    /* najdi prvu cestu -- jednoduchym postupom dopredu */
    for (int i=0; i<N-2; i++) {
      if (koniec->hrana->nasledovnik != NULL) {
        dlzka++;
        clanok = (Spojak*) malloc (sizeof (Spojak));
        clanok->hrana = koniec->hrana->nasledovnik;
        koniec->next = clanok;
        clanok->previous = koniec;
        clanok->next = NULL;
        koniec = clanok;

        cena += clanok->hrana->hodnota;
          // pridaj koncovy vrchol do navstivenych vrcholov
        navstivene_vrcholy[koniec->hrana->koncovy_vrchol]++;
        if (navstivene_vrcholy[koniec->hrana->koncovy_vrchol] == 1)
          pocet_roznych++;
          // oznac hranu ako navstivenu (ale este sme po nej nepresli dopredu)
        koniec->hrana->spracovana = true;
      } else { // ked nemame kam pokracovat
        break;
      }
    }

    if ((pocet_roznych == N) && (cena < najlepsia_cena)) {
      najlepsia_cesta = zaciatok->hrana;
      najlepsia_cena = cena;
    }

    enum Bool nastala_zmena = true;
    while (nastala_zmena == true) { // kym sa cesta zmenila za posledne kolo
      if (zaciatok->hrana->predchodca != NULL) { // ak je kam, hybeme s cestou smerom dozadu
        nastala_zmena = true;
        Spojak* pom = NULL;
        if (dlzka == N-1) {
            // aby sme nemuseli alokovat a dealokovat zbytocne pamat,
            // presunieme uz alokovany "clanok spojaku" z konca na zaciatok
            // len zmenime jeho hodnoty
          cena -= koniec->hrana->hodnota;
          navstivene_vrcholy[koniec->hrana->koncovy_vrchol]--;
          if (navstivene_vrcholy[koniec->hrana->koncovy_vrchol] == 0) {
            pocet_roznych--;
          }
          pom = koniec;
          koniec = koniec->previous;
          koniec->next = NULL;
          pom->hrana = zaciatok->hrana->predchodca->hrana;
          pom->next = zaciatok;
          pom->previous = NULL;
          zaciatok->previous = pom;
        } else { // ak cesta nie je dlha N-1 vrcholov, koniec neposuvame, len pridame zaciatok
          pom = (Spojak*) malloc (sizeof (Spojak));
          pom->hrana = zaciatok->hrana->predchodca->hrana;
          pom->next = zaciatok;
          pom->previous = NULL;
          zaciatok->previous = pom;
          dlzka++;
        }

          // posuniem sa v zozname predchodcov
          // aby som pri dalsom rozhodovani pouzila dalsieho predchodcu v poradi
        zaciatok->hrana->predchodca = zaciatok->hrana->predchodca->next;

        zaciatok = pom;
        zaciatok->hrana->spracovana = true;

        navstivene_vrcholy[zaciatok->hrana->zaciatocny_vrchol]++;
        if (navstivene_vrcholy[zaciatok->hrana->zaciatocny_vrchol] == 1) {
          pocet_roznych++;
        }

        cena += zaciatok->hrana->hodnota;

      } else {
        if (((koniec->hrana->nasledovnik == NULL) && (zaciatok != koniec)) ||
              ((koniec->hrana->nasledovnik != NULL) && (koniec->hrana->nasledovnik->prejdena_vpred == false))) {
              // posuniem sa s cestou dopredu -- pohyb vpred je jednoznacny
              // ale posuniem sa len ak mam nasledovnika, ktorym som este nepresla
              // pripadne ak nemam ziadneho nasledovika, ale este sa cesta moze "skratit"
          nastala_zmena = true;
          cena -= zaciatok->hrana->hodnota;
          navstivene_vrcholy[zaciatok->hrana->zaciatocny_vrchol]--;
          if (navstivene_vrcholy[zaciatok->hrana->zaciatocny_vrchol] == 0) {
            pocet_roznych--;
          }
          zaciatok->hrana->prejdena_vpred = true;
          Spojak* pom = zaciatok;
          zaciatok = zaciatok->next;
          zaciatok->previous = NULL;

          if (koniec->hrana->nasledovnik != NULL) { // pohnem sa koncom dopredu
              // aby sme nemuseli zbytocne alokovat a dealokovat pamat,
              // presunieme uz alokovany "clanok spojaku" zo zaciatku na koniec
              // len zmenime jeho hodnoty
            pom->hrana = koniec->hrana->nasledovnik;
            pom->previous = koniec;
            pom->next = NULL;

            koniec->next = pom;

            koniec = pom;
            koniec->hrana->spracovana = true;

            navstivene_vrcholy[koniec->hrana->koncovy_vrchol]++;
            if (navstivene_vrcholy[koniec->hrana->koncovy_vrchol] == 1) {
              pocet_roznych++;
            }

            cena += koniec->hrana->hodnota;

          } else { // ak nie je kam sa pohnut, "skratim" cestu
            free (pom);
            dlzka--;
          }
        } else { // ked sa nie je kam pohnut ani dopredu, ani dozadu
          nastala_zmena = false;
        }
      }

        // skontrolujem, ci som nasla lepsiu cestu
      if ((pocet_roznych == N) && (cena < najlepsia_cena)) {
          najlepsia_cesta = zaciatok->hrana;
          najlepsia_cena = cena;
      }
    }

      // zvolim si zaciatok novej komponenty z este nespracovanych hran
    while ((zaciatok_komponenty < M) && (hrany[zaciatok_komponenty].spracovana == true)) {
      zaciatok_komponenty++;
    }
  }

    /* vypis vysledok */
  if (najlepsia_cesta != NULL) {
    Hrana* momentalna = najlepsia_cesta;
    printf ("Najlepsia cesta stoji %d a prechadza vrcholmi:\n", najlepsia_cena);
    printf ("%d ", najlepsia_cesta->zaciatocny_vrchol);
    for (int i=0; i<N-1; i++) {
      printf("%d ", momentalna->koncovy_vrchol);
      momentalna = momentalna->nasledovnik;
    }
    printf ("\n");
  } else {
    printf ("Ziadna validna cesta neexistuje.\n");
  }

  return 0;
}