/*
???????????????w????????????wj?????????wj???±j??????f
???????????????????????????????????????????????????
?????????????????????????????????????????????wpgj????????????w
*/
#include<bits/stdc++.h>
 
#define REP(i,s,n) for(int i=s;i<n;i++)
#define rep(i,n) REP(i,0,n)
 
using namespace std;
 
const int IINF = INT_MAX;
struct Edge { int src,dst,weight; };
 
typedef pair<bool,vector<Edge> > boolVectorEdge; // false -> sen, true -> en
typedef pair<int,int> ii;
 
int N,M,K,par[2010],edge_cnt[2010];
vector<int> ver[2010];
vector<boolVectorEdge> graphs;
vector<Edge> edges;
vector<Edge> G[2010];
bool used[2010];
map<ii,int> costs;
 
int find(int i){
  if( i == par[i] ) return i;
  return par[i] = find(par[i]);
}
 
void unit(int x,int y){
  x = find(x), y = find(y);
  if( x != y ) par[x] = y;
}
 
void dfs(int prev,int cur,int index,vector<Edge>& graph){
  int cnt = 0,cnt_sub=0;
  rep(i,G[cur].size()){
    int next = G[cur][i].dst;
    if( next == prev ) continue;
    ++cnt_sub;
    if( cnt_sub == 2 ) {
      assert(used[next]);
      assert( costs.count(ii(cur,next)) );
      graph.push_back((Edge){(int)graph.size()-1,0,costs[ii(cur,next)]});
    }
    if( !used[next] ) { // en no baai mo aru node
      ++cnt;
      used[next] = true;
      assert( costs.count(ii(cur,next)) );
      graph.push_back((Edge){index-1,index,costs[ii(cur,next)]});
      dfs(cur,next,index+1,graph);
    }
  }
  assert( cnt <= 1 );
}
 
void makeGraphs(){
  rep(i,N) par[i] = i;  
  rep(i,M) unit(edges[i].src,edges[i].dst);
  rep(i,N) ver[find(i)].push_back(i);
  rep(i,M) ++edge_cnt[find(edges[i].src)];
  rep(i,2010) if( ver[i].size() ){
    memset(used,false,sizeof(false));
    boolVectorEdge graph;
    graph.first = ( (int)ver[i].size() == edge_cnt[i] ) ;
    int sp = ver[i][0];
    if( !graph.first ) rep(j,ver[i].size()) if( G[ver[i][j]].size() == 1 ) { sp = ver[i][j]; break; }
    graph.second.push_back((Edge){0,0,-IINF});
    used[sp] = true;    
    dfs(-1,sp,1,graph.second);
    graphs.push_back(graph);
  }
 
  /*
  rep(i,graphs.size()) {
    cout << ((graphs[i].first)?"circle":"segment") << endl;
    rep(j,graphs[i].second.size()) {
      cout << "(" << graphs[i].second[j].src << "," << graphs[i].second[j].dst << ":" << graphs[i].second[j].weight << ") " ;
    } 
    puts("");
    puts("");
  }
  */
}
 
int dp1[2010][2010][2][2]; // dp1[i][j][k][l] := i??????§???§j???????????????§i??????¨???£?????????¨????????????(k), 0????????????¨???£?????????¨????????????(l)
int dp2[2010][2010]; // dp2[i][j] := i??????§???§j??????¨???£???
int maxi[2010];
 
void compute(){
  makeGraphs();
  int V = graphs.size();
  rep(i,V+1) rep(j,K+1) dp2[i][j] = -IINF;
  dp2[0][0] = 0;
   
  rep(_,V){
    bool type = graphs[_].first;
    vector<Edge> &G = graphs[_].second;
    rep(i,G.size()+1) rep(j,K+1) rep(k,2) rep(l,2) dp1[i][j][k][l] = -IINF;
    rep(j,2) dp1[0][j][j][j] = 0;
    rep(i,(int)G.size()-1-(type?1:0)){
      rep(j,K+1){
    rep(k,2){
      rep(l,2) if( dp1[i][j][k][l] != -IINF ) {
 
        if( type && i == (int)G.size()-3 ) {
          if( k ) {
        // cur use next use
        if( !( ( l && G[i+2].weight == 0 ) || G[i+1].weight == 0 ) ) {
          int cost = G[i+1].weight;
          if( l ) cost += G[i+2].weight;
          dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]+cost);
          //cout << "xdp1[" << i+1 << "][" << j+1 << "][" << 1 << "][" << l << "] = " << dp1[i+1][j+1][1][l] << " ?? " << "dp1[" << i << "][" << j << "][" << k << "]["<< l << "] = " << dp1[i][j][k][l] << " + " << G[i+2].weight<< endl;
        }
        // cur use next dont use
        dp1[i+1][j][0][l] = max(dp1[i+1][j][0][l],dp1[i][j][k][l]);
        //cout << "ydp1[" << i+1 << "][" << j << "][" << 0 << "][" << l << "] = " << dp1[i+1][j][0][l] << endl;
          } else {
        // cur dont use next use
        if( !( l && G[i+2].weight == 0 ) ) {
          dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]+(l?G[i+2].weight:0));
          //cout << "zdp1[" << i+1 << "][" << j+1 << "][" << 1 << "][" << l << "] = " << dp1[i+1][j+1][1][l] << endl;
          //cout << "dp1[" << i << "][" << j << "][" << k << "][" << l << "] = " << dp1[i][j][k][l] << " + " << G[i+2].weight << endl; 
        }
        // cur dont use next dont use
        dp1[i+1][j][0][l] = max(dp1[i+1][j][0][l],dp1[i][j][k][l]);
        //cout << "dp1[" << i+1 << "][" << j << "][" << 0 << "][" << l << "] = " << dp1[i+1][j][0][l] << endl;
          }
          continue;
        } else {
          // use
          if( k ) {
        if( j+1 <= K && G[i+1].weight != 0 ) {
          dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]+G[i+1].weight);
        }
          } else {
        if( j+1 <= K ) {
          dp1[i+1][j+1][1][l] = max(dp1[i+1][j+1][1][l],dp1[i][j][k][l]);
        }
          }
        }
        // dont use
      INVALID:;
        dp1[i+1][j][0][l] = max(dp1[i+1][j][0][l],dp1[i][j][k][l]);
      }
    }
      }
    }
 
    rep(i,K+1) maxi[i] = -IINF;
    rep(j,K+1) rep(k,2) rep(l,2) {
      maxi[j] = max(maxi[j],dp1[(int)G.size()-1-(type?1:0)][j][k][l]);
      //cout << "maxi[" << j << "] = " << maxi[j] << " dp1[" << (int)G.size()-1-(type?1:0) << "][" << j << "][" << k <<"][" << l << "] = " << dp1[(int)G.size()-1-(type?1:0)][j][k][l] << endl;
    }
    //rep(i,K+1) cout << maxi[i] << " "; puts("");
     
 
    rep(j,K+1) if( dp2[_][j] != -IINF ) {
      rep(j2,K+1) if( maxi[j2] != -IINF ) {
    if( j+j2 <= K ) {
      dp2[_+1][j+j2] = max(dp2[_+1][j+j2],dp2[_][j]+maxi[j2]);
      //cout << "dp2[" << _+1 << "][" << j + j2 << "] = " << dp2[_+1][j+j2] << endl;
    } else break;
      }
    }
  }
  if( dp2[V][K] == -IINF ) puts("Impossible");
  else printf("%d\n",dp2[V][K]);
}
 
int main(){
  scanf("%d %d %d",&N,&M,&K);
  {
    int a,b,c;
    rep(_,M) {
      scanf("%d %d %d",&a,&b,&c);
      --a, --b;
      if( a > b ) swap(a,b);
      costs[ii(a,b)] = costs[ii(b,a)] = c;
      G[a].push_back((Edge){a,b,c});
      G[b].push_back((Edge){b,a,c});
      edges.push_back((Edge){a,b,c});      
    }
  }
  compute();
  return 0;
}

Measured memory_bytes: 66404