DIJKSTRA

#include <bits/stdc++.h>
#define VA AnhNguyenProV2
#define pb push_back
#define ll long long
#define FOR(i, a, b) for(int i = int(a); i <= int(b); i++)
#define FORD(i, a, b) for(int i = int(a); i >= int(b); i--)
#define REP(i, r) for(int i = 0; i < r; i++)
#define FAST ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define READFILE freopen("input.txt", "r", stdin)
#define WRITEFILE freopen("output.txt", "w", stdout);
#define fi first
#define se second
#define MAX 105
#define ii pair<int,int>
using namespace std;

vector<ii> a[MAX];
int d[MAX],n,m, par[MAX], k;

void Dijkstra(int st, int en)
{
    memset(par,0,sizeof par);
    fill(d,d+n+2, INT_MAX);
    d[st]=0;
    priority_queue<ii,vector<ii>,greater<ii>> pq;
    pq.push(ii(0,st));

    while (!pq.empty())
    {
        int u=pq.top().se, du=pq.top().fi;
        pq.pop();
        if (du!=d[u]) continue;
        for(ii t: a[u])
        {
            int v=t.se, uv=t.fi;
            if (du+uv<d[v])
            {
                d[v]=du+uv;
                par[v]=u;
                pq.push(ii(d[v],v));
            }
        }
    }
}

void Trace(int u,int dem)
{
    if (u==0) {cout<<dem<<" ";return;}
    Trace(par[u],dem+1);
    cout<<u<<" ";
}

int main()
{
    #ifndef ONLINE_JUDGE
        READFILE;
    #endif
    FAST;

    cin >> n >> m >> k;
    int u,v,w,cd;

    FOR(i,1,m)
    {
        cin >> u >> v >> w;
        a[u].pb(ii(w,v)); a[v].pb(ii(w,u));
    }

    FOR(i,1,k)
    {
        cin >> cd >> u >> v;
        Dijkstra(u,v);
        if (cd==0) cout<<d[v];
        else Trace(v,0);
        cout<<endl;
    }
    return 0;
}