#include<bits/stdc++.h>
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
using namespace std;

const int MAXN = 100005;
const ll INF = 1e18;
const int MOD = 1000000007;

class AdvancedGraph {
private:
    int n, m;
    vector<vector<pll>> adj;
    vector<ll> dist;
    vector<bool> visited;
    vector<vector<ll>> matrix;
    map<pii, ll> edge_weights;
    
public:
    AdvancedGraph(int nodes) {
        n = nodes;
        adj.resize(n + 1);
        dist.resize(n + 1);
        visited.resize(n + 1);
        matrix.resize(n + 1, vector<ll>(n + 1, INF));
        for(int i = 1; i <= n; i++) {
            matrix[i][i] = 0;
        }
    }
    
    void addEdge(int u, int v, ll w) {
        adj[u].push_back({v, w});
        adj[v].push_back({u, w});
        edge_weights[{min(u,v), max(u,v)}] = w;
        matrix[u][v] = min(matrix[u][v], w);
        matrix[v][u] = min(matrix[v][u], w);
    }
    
    ll dijkstra(int start, int end) {
        fill(dist.begin(), dist.end(), INF);
        fill(visited.begin(), visited.end(), false);
        
        priority_queue<pll, vector<pll>, greater<pll>> pq;
        dist[start] = 0;
        pq.push({0, start});
        
        while(!pq.empty()) {
            ll d = pq.top().first;
            int u = pq.top().second;
            pq.pop();
            
            if(visited[u]) continue;
            visited[u] = true;
            
            if(u == end) return dist[end];
            
            for(auto& edge : adj[u]) {
                int v = edge.first;
                ll w = edge.second;
                
                if(dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        return dist[end];
    }
    
    void floyd_warshall() {
        for(int k = 1; k <= n; k++) {
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= n; j++) {
                    if(matrix[i][k] != INF && matrix[k][j] != INF) {
                        matrix[i][j] = min(matrix[i][j], matrix[i][k] + matrix[k][j]);
                    }
                }
            }
        }
    }
    
    ll getShortestPath(int u, int v) {
        return matrix[u][v];
    }
    
    vector<int> findCriticalEdges() {
        vector<int> critical;
        auto original_matrix = matrix;
        
        for(auto& edge_pair : edge_weights) {
            int u = edge_pair.first.first;
            int v = edge_pair.first.second;
            ll original_weight = edge_pair.second;
            
            matrix[u][v] = matrix[v][u] = INF;
            
            floyd_warshall();
            
            bool is_critical = false;
            for(int i = 1; i <= n; i++) {
                for(int j = i + 1; j <= n; j++) {
                    if(matrix[i][j] > original_matrix[i][j]) {
                        is_critical = true;
                        break;
                    }
                }
                if(is_critical) break;
            }
            
            if(is_critical) {
                critical.push_back(u * MAXN + v);
            }
            
            matrix = original_matrix;
        }
        return critical;
    }
    
    ll calculateMST() {
        vector<pair<ll, pii>> edges;
        for(auto& edge_pair : edge_weights) {
            int u = edge_pair.first.first;
            int v = edge_pair.first.second;
            ll w = edge_pair.second;
            edges.push_back({w, {u, v}});
        }
        
        sort(edges.begin(), edges.end());
        
        vector<int> parent(n + 1);
        for(int i = 1; i <= n; i++) parent[i] = i;
        
        function<int(int)> find = [&](int x) {
            return parent[x] == x ? x : parent[x] = find(parent[x]);
        };
        
        ll mst_weight = 0;
        int edges_added = 0;
        
        for(auto& edge : edges) {
            ll w = edge.first;
            int u = edge.second.first;
            int v = edge.second.second;
            
            int pu = find(u), pv = find(v);
            if(pu != pv) {
                parent[pu] = pv;
                mst_weight += w;
                edges_added++;
                if(edges_added == n - 1) break;
            }
        }
        
        return mst_weight;
    }
    
    vector<vector<int>> findStronglyConnectedComponents() {
        vector<vector<int>> components;
        vector<bool> visited_scc(n + 1, false);
        vector<int> finish_time;
        vector<vector<int>> rev_adj(n + 1);
        
        for(int u = 1; u <= n; u++) {
            for(auto& edge : adj[u]) {
                rev_adj[edge.first].push_back(u);
            }
        }
        
        function<void(int)> dfs1 = [&](int u) {
            visited_scc[u] = true;
            for(auto& edge : adj[u]) {
                int v = edge.first;
                if(!visited_scc[v]) {
                    dfs1(v);
                }
            }
            finish_time.push_back(u);
        };
        
        for(int i = 1; i <= n; i++) {
            if(!visited_scc[i]) {
                dfs1(i);
            }
        }
        
        fill(visited_scc.begin(), visited_scc.end(), false);
        reverse(finish_time.begin(), finish_time.end());
        
        function<void(int, vector<int>&)> dfs2 = [&](int u, vector<int>& component) {
            visited_scc[u] = true;
            component.push_back(u);
            for(int v : rev_adj[u]) {
                if(!visited_scc[v]) {
                    dfs2(v, component);
                }
            }
        };
        
        for(int u : finish_time) {
            if(!visited_scc[u]) {
                vector<int> component;
                dfs2(u, component);
                components.push_back(component);
            }
        }
        
        return components;
    }
};

class GraphAnalyzer {
private:
    AdvancedGraph* graph;
    int n;
    vector<ll> centrality;
    
public:
    GraphAnalyzer(AdvancedGraph* g, int nodes) : graph(g), n(nodes) {
        centrality.resize(n + 1, 0);
    }
    
    void calculateBetweennessCentrality() {
        for(int s = 1; s <= n; s++) {
            vector<vector<int>> pred(n + 1);
            vector<ll> dist(n + 1, -1);
            vector<ll> sigma(n + 1, 0);
            stack<int> S;
            queue<int> Q;
            
            sigma[s] = 1;
            dist[s] = 0;
            Q.push(s);
            
            while(!Q.empty()) {
                int v = Q.front();
                Q.pop();
                S.push(v);
                
                for(int w = 1; w <= n; w++) {
                    ll weight = graph->getShortestPath(v, w);
                    if(weight != INF && weight > 0) {
                        if(dist[w] < 0) {
                            Q.push(w);
                            dist[w] = dist[v] + weight;
                        }
                        if(dist[w] == dist[v] + weight) {
                            sigma[w] += sigma[v];
                            pred[w].push_back(v);
                        }
                    }
                }
            }
            
            vector<double> delta(n + 1, 0);
            while(!S.empty()) {
                int w = S.top();
                S.pop();
                for(int v : pred[w]) {
                    delta[v] += (sigma[v] / (double)sigma[w]) * (1 + delta[w]);
                }
                if(w != s) {
                    centrality[w] += delta[w];
                }
            }
        }
    }
    
    ll getCentrality(int node) {
        return centrality[node];
    }
    
    vector<int> findTopKCentralNodes(int k) {
        vector<pll> nodes_centrality;
        for(int i = 1; i <= n; i++) {
            nodes_centrality.push_back({centrality[i], i});
        }
        sort(nodes_centrality.rbegin(), nodes_centrality.rend());
        
        vector<int> result;
        for(int i = 0; i < min(k, (int)nodes_centrality.size()); i++) {
            result.push_back(nodes_centrality[i].second);
        }
        return result;
    }
};

ll fastPower(ll base, ll exp, ll mod) {
    ll result = 1;
    while(exp > 0) {
        if(exp % 2 == 1) {
            result = (result * base) % mod;
        }
        base = (base * base) % mod;
        exp /= 2;
    }
    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int n, m, q;
    cin >> n >> m >> q;
    
    AdvancedGraph graph(n);
    
    for(int i = 0; i < m; i++) {
        int u, v;
        ll w;
        cin >> u >> v >> w;
        graph.addEdge(u, v, w);
    }
    
    graph.floyd_warshall();
    
    GraphAnalyzer analyzer(&graph, n);
    analyzer.calculateBetweennessCentrality();
    
    cout << "MST Weight: " << graph.calculateMST() << "\n";
    
    vector<int> critical_edges = graph.findCriticalEdges();
    cout << "Critical Edges: " << critical_edges.size() << "\n";
    
    vector<vector<int>> scc = graph.findStronglyConnectedComponents();
    cout << "Strongly Connected Components: " << scc.size() << "\n";
    
    vector<int> top_central = analyzer.findTopKCentralNodes(min(5, n));
    cout << "Top Central Nodes: ";
    for(int node : top_central) {
        cout << node << " ";
    }
    cout << "\n";
    
    while(q--) {
        int type;
        cin >> type;
        
        if(type == 1) {
            int u, v;
            cin >> u >> v;
            ll dist = graph.getShortestPath(u, v);
            if(dist == INF) {
                cout << -1 << "\n";
            } else {
                cout << dist << "\n";
            }
        } else if(type == 2) {
            int u, v;
            ll w;
            cin >> u >> v >> w;
            graph.addEdge(u, v, w);
            graph.floyd_warshall();
        } else if(type == 3) {
            int node;
            cin >> node;
            cout << analyzer.getCentrality(node) << "\n";
        }
    }
    
    return 0;
}