#include <bits/stdc++.h>
// #include "ane.cpp"

const int INF  = 1e9;
const long long INFLL = 1e18;
const int NMAX = 100005;
const int MMAX = 200005;
const int KMAX = 1005;
const int MOD  = 1e9 + 7;
using namespace std;

// comment to disable debug functions
// #define DEBUG

// frequently used macros

#if __cplusplus >= 201103L
#define ALL(v) begin(v),end(v)
#define SORT(v) sort(begin(v), end(v))
#define FIND(v,x) find(begin(v), end(v), (x))
#else
#define ALL(v) (v).begin(),(v).end()
#define SORT(v) sort(v.begin(), v.end())
#define FIND(v,x) find(v.begin(), v.end(), (x))
#endif

#define MEMNEXT(from, to) do{ memmove((to), (from), sizeof(from)); \
  memset((from), 0, sizeof(from)); } while(0)

#ifdef DEBUG
#define DUMP(x) do{ std::cerr << "(DUMP) " << (#x) << ": " << x << std::endl; }while(0)
#else
#define DUMP(x) do{}while(0)
#endif

// frequent used aliases
typedef long long ll;
typedef pair<int, int> p;
typedef pair<ll, int> lp;
typedef pair<ll, ll> pll;
typedef vector<int> vec;
typedef vector<ll> vecll;
typedef vector<vec> mat;
typedef vector<vecll> matll;

// frequently used constants
static const int di[] = {-1, 0, 1, -1, 1, -1, 0, 1};
static const int dj[] = {-1, -1, -1, 0, 0, 1, 1, 1};

// frequently used structs
struct edge{
  ll to,cost;
};

// printf for debug
#ifndef DEBUG
void debug(const char* format, ...){}
#else
void debug(const char* format, ...){
  va_list arg;
  va_start(arg, format);
  vprintf(format, arg);
  va_end(arg);
}
#endif

// dump vector
#ifdef DEBUG
#define DUMPV(v, _end) do{       \
  printf("%s: ", #v);         \
  for (auto ite = begin(v); ite != (_end); ++ite) \
  {                           \
  cout << *ite << " ";      \
  }                           \
  cout << endl;               \
} while(0)
#else
#define DUMPV(v,c)
#endif

// std::fill of multi dimensions
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
  std::fill( (T*)array, (T*)(array+N), val );
}

// binary search
ll BSearch(ll _begin, ll _end, bool (*f)(int)){
  ll mid;
  while(_end - _begin > 1LL) {
  mid = (_begin + _end) / 2LL;
  if(f(mid)) {
    debug("BSearch: f(%d) == true\n", mid);
    _end = mid;
  }
  else
  {
    debug("BSearch: f(%d) == false\n", mid);
    _begin = mid;
  }
  }
  return _end;
}


ll N,M,K,A[MMAX],B[MMAX],C,D[MMAX],E;
ll d[NMAX] = {};
bool inside[NMAX] = {};
std::vector<edge> G[NMAX];
multimap<ll, int> mp;
ll ans = INFLL;

void solve(){
  // main algorithm
  // dijkstra
  Fill(d, INFLL);
  priority_queue<lp, vector<lp>, greater<lp> > que;
  que.push(lp(0LL, 1));
  while(!que.empty()) {
    ll dd = que.top().first;
    int i = que.top().second;
    que.pop();
    if(d[i] <= dd) continue;
    d[i] = dd;
    for(auto&& e : G[i]) {
      if(d[e.to] > dd + e.cost) que.push(lp(dd + e.cost, e.to));
    }
  }
  // sort by dist
  for (int i = 1; i <= N; ++i)
  {
    mp.insert(make_pair(d[i], i));
  }
  // calc edges inside and minimum
  debug("points:\n");
  const ll sum = accumulate(D, D + M, 0LL);
  ll points = 0;

  for(auto p = mp.begin(); p != mp.end();) {
    ll dd = p->first;

    int cnt = mp.count(dd);
    for(int c = 0; c < cnt; ++c, ++p){
      int i = p->second;
      inside[i] = true;
      for(auto&& e : G[i])
        if(inside[e.to]) points += e.cost;
    }

    debug("%lld : %lld\n", dd, points);
    debug("ans = min(%lld, %lld)\n", ans, C * dd + (sum - points));
    ans = min(ans, C * dd + (sum - points));
  }
}
void debug(){
  // output debug information
  cout << "d:\n";
  for(int i=0; i < N; ++i) {
    cout << i+1 << " : " <<  d[i+1] << "\n";
  }

  cout << "mp:\n";
  for(auto&& p : mp) {
    cout << p.first << " -> " << p.second << endl;
  }

}
void answer(){
  // output answer
  printf("%lld\n", ans);
}
int main(int argc, char const *argv[])
{
  // operate inputs

  // Fill(dp, -1);
  scanf("%lld%lld%lld", &N,&M, &C);
  for (int i = 0; i < M; ++i)
  {
    scanf("%lld%lld%lld", &A[i], &B[i], &D[i]);
    G[A[i]].push_back(edge{B[i], D[i]});
    G[B[i]].push_back(edge{A[i], D[i]});
  }
  solve();
  #ifdef DEBUG
  debug();
  #endif
  answer();

  return 0;
}
### Prompt

Generate a CPP solution to the following problem:

JOI Park

In preparation for the Olympic Games in IOI in 20XX, the JOI Park in IOI will be developed. There are N squares in JOI Park, and the squares are numbered from 1 to N. There are M roads connecting the squares, and the roads are numbered from 1 to M. The road i (1 ≤ i ≤ M) connects the square Ai and the square Bi in both directions, and the length is Di. You can follow several paths from any square to any square.

In the maintenance plan, first select an integer X of 0 or more, and connect all the squares (including square 1) whose distance from square 1 is X or less to each other by an underpass. However, the distance between the square i and the square j is the minimum value of the sum of the lengths of the roads taken when going from the square i to the square j. In the maintenance plan, the integer C for the maintenance cost of the underpass is fixed. The cost of developing an underpass is C x X.

Next, remove all the roads connecting the plazas connected by the underpass. There is no cost to remove the road. Finally, repair all the roads that remained unremoved. The cost of repairing a road of length d is d. There is no underpass in JOI Park before the implementation of the maintenance plan. Find the minimum sum of the costs of developing the JOI Park.

Task

Given the information on the JOI Park Square and an integer for the underpass maintenance cost, create a program to find the minimum sum of the costs for the JOI Park maintenance.

input

Read the following data from standard input.

* On the first line, the integers N, M, and C are written with blanks as delimiters. This means that there are N squares, M roads, and the integer for the underpass maintenance cost is C.
* On the i-th line (1 ≤ i ≤ M) of the following M lines, the integers Ai, Bi, and Di are written separated by blanks. This means that the road i connects the square Ai and the square Bi, and the length is Di.



output

Output an integer representing the minimum sum of the costs of developing the JOI park to the standard output on one line.

Limits

All input data satisfy the following conditions.

* 2 ≤ N ≤ 100 000.
* 1 ≤ M ≤ 200 000.
* 1 ≤ C ≤ 100 000.
* 1 ≤ Ai ≤ N (1 ≤ i ≤ M).
* 1 ≤ Bi ≤ N (1 ≤ i ≤ M).
* Ai ≠ Bi (1 ≤ i ≤ M).
* (Ai, Bi) ≠ (Aj, Bj) and (Ai, Bi) ≠ (Bj, Aj) (1 ≤ i <j ≤ M).
* 1 ≤ Di ≤ 100 000 (1 ≤ i ≤ M).
* With the input data given, it is guaranteed that you can go from any square to any square by following several paths.



Input / output example

Input example 1


5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5


Output example 1


14


In this input example, when X = 3, the sum of the maintenance costs when all the squares (square 1, square 2, square 3) whose distance from square 1 is 3 or less are connected to each other by an underpass. Is 2 × 3 + 3 + 5 = 14. This is the minimum value.

Input example 2


5 4 10
one two Three
2 3 4
3 4 3
4 5 5


Output example 2


15


In this input example, the sum of maintenance costs is minimized when X = 0.

Input example 3


6 5 2
1 2 2
1 3 4
1 4 3
1 5 1
1 6 5


Output example 3


Ten


In this input example, when all the squares are connected to each other by an underpass with X = 5, the sum of the maintenance costs is minimized.

The question text and the data used for the automatic referee are the question text and the test data for scoring, which are created and published by the Japan Committee for Information Olympics.





Example

Input

5 5 2
2 3 1
3 1 2
2 4 3
1 2 4
2 5 5


Output

14

### Response

```cpp
#include <bits/stdc++.h>
// #include "ane.cpp"

const int INF  = 1e9;
const long long INFLL = 1e18;
const int NMAX = 100005;
const int MMAX = 200005;
const int KMAX = 1005;
const int MOD  = 1e9 + 7;
using namespace std;

// comment to disable debug functions
// #define DEBUG

// frequently used macros

#if __cplusplus >= 201103L
#define ALL(v) begin(v),end(v)
#define SORT(v) sort(begin(v), end(v))
#define FIND(v,x) find(begin(v), end(v), (x))
#else
#define ALL(v) (v).begin(),(v).end()
#define SORT(v) sort(v.begin(), v.end())
#define FIND(v,x) find(v.begin(), v.end(), (x))
#endif

#define MEMNEXT(from, to) do{ memmove((to), (from), sizeof(from)); \
  memset((from), 0, sizeof(from)); } while(0)

#ifdef DEBUG
#define DUMP(x) do{ std::cerr << "(DUMP) " << (#x) << ": " << x << std::endl; }while(0)
#else
#define DUMP(x) do{}while(0)
#endif

// frequent used aliases
typedef long long ll;
typedef pair<int, int> p;
typedef pair<ll, int> lp;
typedef pair<ll, ll> pll;
typedef vector<int> vec;
typedef vector<ll> vecll;
typedef vector<vec> mat;
typedef vector<vecll> matll;

// frequently used constants
static const int di[] = {-1, 0, 1, -1, 1, -1, 0, 1};
static const int dj[] = {-1, -1, -1, 0, 0, 1, 1, 1};

// frequently used structs
struct edge{
  ll to,cost;
};

// printf for debug
#ifndef DEBUG
void debug(const char* format, ...){}
#else
void debug(const char* format, ...){
  va_list arg;
  va_start(arg, format);
  vprintf(format, arg);
  va_end(arg);
}
#endif

// dump vector
#ifdef DEBUG
#define DUMPV(v, _end) do{       \
  printf("%s: ", #v);         \
  for (auto ite = begin(v); ite != (_end); ++ite) \
  {                           \
  cout << *ite << " ";      \
  }                           \
  cout << endl;               \
} while(0)
#else
#define DUMPV(v,c)
#endif

// std::fill of multi dimensions
template<typename A, size_t N, typename T>
void Fill(A (&array)[N], const T &val){
  std::fill( (T*)array, (T*)(array+N), val );
}

// binary search
ll BSearch(ll _begin, ll _end, bool (*f)(int)){
  ll mid;
  while(_end - _begin > 1LL) {
  mid = (_begin + _end) / 2LL;
  if(f(mid)) {
    debug("BSearch: f(%d) == true\n", mid);
    _end = mid;
  }
  else
  {
    debug("BSearch: f(%d) == false\n", mid);
    _begin = mid;
  }
  }
  return _end;
}


ll N,M,K,A[MMAX],B[MMAX],C,D[MMAX],E;
ll d[NMAX] = {};
bool inside[NMAX] = {};
std::vector<edge> G[NMAX];
multimap<ll, int> mp;
ll ans = INFLL;

void solve(){
  // main algorithm
  // dijkstra
  Fill(d, INFLL);
  priority_queue<lp, vector<lp>, greater<lp> > que;
  que.push(lp(0LL, 1));
  while(!que.empty()) {
    ll dd = que.top().first;
    int i = que.top().second;
    que.pop();
    if(d[i] <= dd) continue;
    d[i] = dd;
    for(auto&& e : G[i]) {
      if(d[e.to] > dd + e.cost) que.push(lp(dd + e.cost, e.to));
    }
  }
  // sort by dist
  for (int i = 1; i <= N; ++i)
  {
    mp.insert(make_pair(d[i], i));
  }
  // calc edges inside and minimum
  debug("points:\n");
  const ll sum = accumulate(D, D + M, 0LL);
  ll points = 0;

  for(auto p = mp.begin(); p != mp.end();) {
    ll dd = p->first;

    int cnt = mp.count(dd);
    for(int c = 0; c < cnt; ++c, ++p){
      int i = p->second;
      inside[i] = true;
      for(auto&& e : G[i])
        if(inside[e.to]) points += e.cost;
    }

    debug("%lld : %lld\n", dd, points);
    debug("ans = min(%lld, %lld)\n", ans, C * dd + (sum - points));
    ans = min(ans, C * dd + (sum - points));
  }
}
void debug(){
  // output debug information
  cout << "d:\n";
  for(int i=0; i < N; ++i) {
    cout << i+1 << " : " <<  d[i+1] << "\n";
  }

  cout << "mp:\n";
  for(auto&& p : mp) {
    cout << p.first << " -> " << p.second << endl;
  }

}
void answer(){
  // output answer
  printf("%lld\n", ans);
}
int main(int argc, char const *argv[])
{
  // operate inputs

  // Fill(dp, -1);
  scanf("%lld%lld%lld", &N,&M, &C);
  for (int i = 0; i < M; ++i)
  {
    scanf("%lld%lld%lld", &A[i], &B[i], &D[i]);
    G[A[i]].push_back(edge{B[i], D[i]});
    G[B[i]].push_back(edge{A[i], D[i]});
  }
  solve();
  #ifdef DEBUG
  debug();
  #endif
  answer();

  return 0;
}
```