#include <stdlib.h>
#include <stdio.h>
#include <cassert>
#include <fstream>
#include <time.h>
#include <iostream>
#include <limits.h>

using namespace std;

int numVertices, numEdges, Q, *Q_o;
int *parent, *w, numTrees;
int *bestEdgeNum;

struct edge{
  int u,v,w;
};


int find(int x){
  int i,j,root;

  for(i=x; parent[i]!=i;i=parent[i]);
   root=i;

  for(i=x;parent[i]!=i;j=parent[i],parent[i]=root,i=j);
  return root;
}

void makeEquivalent(int i, int j)
{
  if(w[i]>w[j])
  {
    parent[j]=i;
    w[i]+=w[j];
  }
  else
  {
    parent[i]=j;
    w[j]+=w[i];
  }
  numTrees--;
}

int main(){
  struct edge *edge_graph;
  long int MST_cost = 0;
  int root1 = 0, root2 = 0;
  int usefulEdges = 0;
  int temp = 0;


  ifstream fin("input.txt");assert(fin);

  fin >> numVertices;
  fin >> numEdges;
  fin >> Q;

  edge_graph = (struct edge*)malloc(numEdges*sizeof(struct edge));
  parent = (int*)malloc(numVertices*sizeof(int));
  w = (int*)malloc(numVertices*sizeof(int));
  bestEdgeNum = (int*)malloc(numVertices*sizeof(int));
  Q_o = (int*)malloc(Q*sizeof(int));


  for(int i = 0; i < numEdges; i++)
  {
    fin >> edge_graph[i].u;
    fin >> edge_graph[i].v;
    fin >> edge_graph[i].w;

//edge_graph[i].u--;
//edge_graph[i].v--;
  }

 fin.close();
  for(int i = 0; i < Q; i++)
    Q_o[i] = INT_MAX;

  for(int i = 0; i<numVertices; i++)
  {
    parent[i] = i;
    w[i]=1;
  }

  numTrees = numVertices;
  usefulEdges = numEdges;

  while(numTrees>1 && usefulEdges>0)
  {
    for(int i = 0; i<numVertices;i++)
      bestEdgeNum[i] = (-1);
    usefulEdges =0;

    for (int i = 0; i<numEdges;i++)
    {
      root1 = find(edge_graph[i].u);
      root2 = find(edge_graph[i].v);

      if(root1==root2)
        cout << "";
      else
      {


        usefulEdges++;
        if(bestEdgeNum[root1] == (-1) || edge_graph[bestEdgeNum[root1]].w > edge_graph[i].w)
          bestEdgeNum[root1] = i;
        
        if(bestEdgeNum[root2] == (-1) || edge_graph[bestEdgeNum[root2]].w > edge_graph[i].w)
          bestEdgeNum[root2] = i;
      }
    }    
    //for(int i = 0; i<numVertices;i++)
    //  cout << bestEdgeNum[i]<< endl;
    //cout << "---" << endl;
    for(int i = 0; i<numVertices;i++)
    {
      if(bestEdgeNum[i]!=(-1))
      {

        root1 = find(edge_graph[bestEdgeNum[i]].u);
        root2 = find(edge_graph[bestEdgeNum[i]].v);

        if(root1 == root2)
          continue;


        if(bestEdgeNum[i]<Q)
          Q_o[bestEdgeNum[i]] = 0;


          for(int k = 0; k < Q; k++)
          {
            if(Q_o[k] !=0)
            {
              if( edge_graph[k].u == edge_graph[bestEdgeNum[i]].u  || 
                  edge_graph[k].v == edge_graph[bestEdgeNum[i]].u || 
                  edge_graph[k].u == edge_graph[bestEdgeNum[i]].v || 
                  edge_graph[k].v == edge_graph[bestEdgeNum[i]].v)
              {
                temp = (edge_graph[k].w-edge_graph[bestEdgeNum[i]].w);
                if(temp!=0)
                  Q_o[k] = min(Q_o[k], temp);
                    
              }
            }
          }
      
        MST_cost += edge_graph[bestEdgeNum[i]].w;
        makeEquivalent(root1,root2);
       
      }
    }

  }

  ofstream fout("output.txt"); 
  fout <<  MST_cost << endl;

  for(int i = 0; i < Q; i++)
    fout << Q_o[i] << endl;

  fout.close();
  free(edge_graph);
  free(parent);
  free(w);
  free(bestEdgeNum);
  free(Q_o);

}