TaiTrong

#include <bits/stdc++.h>

using namespace std;

int a[25][25], trace[25], ways[25], n, s, t, ans, m;
vector <int> b;

void DFS(int u, int w) {
    for (int v=1; v<=n; ++v)
        if (trace[v]==0 && a[u][v]>0 && a[u][v]>=w) {
            trace[v]=u; DFS(v, w);
        }
}

void solve(int w) {
    memset(trace, 0, sizeof(trace)); trace[s]=-1;
    DFS(s, w);

    if (trace[t]!=0 && w>ans) {
        ans=w;

        int tmp=t; m=0;
        while (tmp!=s) {
            ways[m++]=tmp; tmp=trace[tmp];
        }
        ways[m]=s;
    }
}

int main() {
    freopen("taitrong.inp", "r", stdin);

    scanf("%d%d%d", &n, &s, &t);
    memset(a, 0, sizeof(a)); ans=-1;
    int u, v, w;
    while (scanf("%d%d%d", &u, &v, &w) != EOF) {
        a[u][v]=a[v][u]=w;
        b.push_back(w);
    }

    int vec=b.size(); bool done[10005];
    memset(done, false, sizeof(done));
    for (int i=0; i<vec; ++i)
        if (!done[b[i]]) {
            solve(b[i]); done[b[i]]=true;
        }

    printf("%d\n", ans);
    for (int i=m; i>=0; i--) printf("%d ", ways[i]);

    return 0;
}