#include <fstream>
using namespace std;

const int INF = 2147483647;
const int MAX_N = 10000;
const int MAX_M = 1000000;
int m, n, q;

int matrix[MAX_N][MAX_N];
int costo_totale_archi[MAX_N];

int myMin(int a, int b){
    return a<b ? a : b;
}

int getMax(int array[], int size){
    int max = 0;
    for(int i=0; i<size; i++){
        if (array[i]>max)
            max = array[i];
    }

    return max;
}


int main() {
  ifstream fin("input.txt");
  fin >> n >> m >> q;

  for(int i=0; i<n; i++){
      for(int j=0; j<n; j++){
        matrix[i][j] = -1;
      }
      costo_totale_archi[i] = INF;
  }

  costo_totale_archi[0] = 0;

  for(int k=0; k<m; k++){
     int v, u, w;
     fin >> v >> u >> w;
     matrix[v-1][u-1] = w;
     matrix[u-1][v-1] = w;      //il grafo è indiretto
  }
  fin.close();

  for(int i=0; i<n; i++){
      for(int j=1; j<n; j++){
          if (matrix[i][j] >= 0){
            costo_totale_archi[j] = myMin(costo_totale_archi[j], costo_totale_archi[j-1]+ matrix[i][j]);
          }
      }
  }

  ofstream fout("output.txt");
  fout << getMax(costo_totale_archi, n) << "\n";
  fout.close();
  return 0;
}