#include <bits/stdc++.h>

using namespace std;
const int INF = 1e9;
const int NMAX = 1000005;
const int BMAX = 1e5;
ifstream fin ("harta.in");
ofstream fout ("harta.out");
vector < pair < int , int > > G[NMAX],Gj[NMAX];
vector < int > T,TJ,TR;
int DR[NMAX],DJ[NMAX],poz = BMAX - 1;
char buffer[BMAX + 5];
void parsare(int &x){
    while(!isdigit(buffer[poz])){
        poz++;
        if(poz == BMAX){
            fin.read(buffer,BMAX);
            poz = 0;
        }
    }
    x = 0;
    while(isdigit(buffer[poz])){
        x = x*10 + (buffer[poz] - '0');
        poz++;
        if(poz == BMAX){
            fin.read(buffer,BMAX);
            poz = 0;
        }
    }
}




bool cmpj(const int &a,const int &b){
return DJ[a] > DJ[b];
}
bool cmpr(const int &a,const int &b){
return DR[a] > DR[b];
}
int dijkstraj(int n){
    for(int i = 1; i <= n; i++)
        DJ[i] = INF;
    DJ[T.front()] = 0;
    int nod;
    while(!T.empty()){
        nod = T.front();
        pop_heap(T.begin(),T.end(),cmpj);
        T.pop_back();
        for(int i = 0; i < G[nod].size();i++){
            if(DJ[G[nod][i].first] > G[nod][i].second + DJ[nod]){
                DJ[G[nod][i].first] = G[nod][i].second + DJ[nod];
                T.push_back(G[nod][i].first);
                push_heap(T.begin(),T.end(),cmpj);
            }
        }
    }
}
int dijkstrar(int n){
    for(int i = 1; i <= n; i++)
        DR[i] = INF;
    DR[T.front()] = 0;
    int nod;
    while(!T.empty()){
        nod = T.front();
        pop_heap(T.begin(),T.end(),cmpr);
        T.pop_back();
        for(int i = 0; i < G[nod].size();i++){
            if(DR[G[nod][i].first] > G[nod][i].second + DR[nod]){
                DR[G[nod][i].first] = G[nod][i].second + DR[nod];
                T.push_back(G[nod][i].first);
                push_heap(T.begin(),T.end(),cmpr);
            }
        }
    }
}

void traseuj(int nod){
    for(int i = 0; i < Gj[nod].size(); i++){
        if(DJ[Gj[nod][i].first] + Gj[nod][i].second == DJ[nod]){
            traseuj(Gj[nod][i].first);
        }
    }
    TJ.push_back(nod);
}
void traseur(int nod){
    for(int i = 0; i < Gj[nod].size(); i++){
        if(DR[Gj[nod][i].first] + Gj[nod][i].second == DR[nod]){
            traseur(Gj[nod][i].first);
        }
    }
    TR.push_back(nod);

}
int main()
{
    int n,m,x,y,d;
    parsare(n); parsare(m);
    for(int i = 1; i <= m; i++){
        parsare(x); parsare(y); parsare(d);
        G[x].push_back({y,d});
        Gj[y].push_back({x,d});
    }
    parsare(x); parsare(y);
    T.push_back(x);
    make_heap(T.begin(),T.end(),cmpj);
    dijkstraj(n);
    T.push_back(y);
    make_heap(T.begin(),T.end(),cmpr);
    dijkstrar(n);
    int M = INF,nod;
    for(int i = 1; i <= n; i++){
        if(DR[i] + DJ[i] < M){
            M = DR[i] + DJ[i];
            nod = i;
        }
    }
    traseuj(nod);
    traseur(nod);
    fout << "Intersectia: " << nod <<"\n";
    fout << "Julieta parcurge: " << DJ[nod] << "\n";
    fout << "Romeo parcurge: " << DR[nod] << "\n";
    fout << "Traseul Julietei: ";
    for(int i = 0 ; i < TJ.size();i++)
        fout << TJ[i] << " ";
    fout <<"\n"<< "Traseul lui Romeo: ";
    for(int i = 0 ; i < TR.size();i++)
        fout << TR[i] << " ";

    return 0;
}