stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include <bits/stdc++.h>

#define up(i,a,b) for(int i=a;i<=b;i++)

#define down(i,a,b) for(int i=a;i>=b;i--)

#define rep(i,a,b) for(int i=a;i<b;i++)

#define repd(i,a,b) for(int i=a-1;i>=b;i--)

#define CL(x) (x<<1)

#define CR(x) (x<<1)+1

#define pb push_back

#define bit1(x) __builtin_popcount(x)



using namespace std;



typedef long long ll;

typedef pair<int,int> pii;



template<typename T> inline void _read(T &x){

    char ch; x=0; bool neg=false;

    for(ch=getchar();ch<'0'||ch>'9';ch=getchar())

        if(ch=='-') neg=true;

    for(;ch>='0'&&ch<='9';ch=getchar()) x=10*x+ch-'0';

    if(neg) x=-x;

}

#define read(a) _read(a)

#define Read(a,b) _read(a),_read(b)



const int maxn=1e5+7;

const int maxS=(1<<6);

const ll mod=1e9;

const int inf=1e9+7;

const ll linf=1e16+9;



int n,t[maxn],kq;

struct Neko{

    int x,y;

}a[maxn];



inline void Enter(){

    cin>>n;

    up(i,1,n) cin>>t[i]>>a[i].x>>a[i].y;

}



inline int dis(Neko x,Neko y){

    return abs(x.x-y.x)+abs(x.y-y.y);

}



inline void Solve(){

    up(i,1,n){

        int Time=t[i]-t[i-1];

        if(dis(a[i],a[i-1])%2 == Time%2 && dis(a[i],a[i-1])<=Time) kq++;

    }

    if(kq!=n) cout<<"No";

    else cout<<"Yes";

}



int main(){

    ios_base::sync_with_stdio(false);

    cin.tie(NULL),cout.tie(NULL);

    //freopen("TEST.INP","r",stdin);

    //freopen("TEST.OUT","w",stdout);



    Enter();

    Solve();



    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.346137897125119x):
#include<stdio.h>

int t[100010],x[100010],y[100010];

int main()

{

    int n,sum=0;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d%d%d",&t[i],&x[i],&y[i]);

    for(int i=1;i<=n;i++)

    {

        sum=x[i]+y[i]-x[i-1]-y[i-1];

        if((t[i]-t[i-1])<sum)

        {

            printf("No\n");

            return 0;

        }

        if((sum-(t[i]-t[i-1]))%2)

        {

            printf("No\n");

            return 0;

        }

    }

    printf("Yes\n");

    return 0;

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

#include <set>

#include <map>

#include <cassert>

#include <queue>

#include <vector>

#define CL(a) memset(a,0,sizeof(a))

#define cl(a,b) memset(a,(b),sizeof(a))

#define For(i,a,b) for(int i=a;i<=b;i++)

#define _for(i,a,b) for(int i=a;i<b;i++)

#define LL long long 

using namespace std;

const int maxn = 1e5 + 100;

struct Point{

	int t,x,y;

	bool operator < (const Point& p)const

	{

		return t<p.t;

	}

}a[maxn]; 

int main()

{

	//freopen("in.txt","r",stdin);

    int n;

	scanf("%d",&n);

	a[0].t = a[0].x = a[0].y = 0;

	for(int i=1;i<=n;i++)

	{

		scanf("%d%d%d",&a[i].t,&a[i].x,&a[i].y);	

	}   

	sort(a,a+n+1);

	int flag = true;

	for(int i=1;i<=n&&flag;i++)

	{

		int tt = a[i].t - a[i-1].t;

		int dis = abs(a[i].x-a[i-1].x)+abs(a[i].y-a[i-1].y);

		if(dis>tt) flag = 0;

		if((tt-dis)%2) flag = 0;

	}

	if(flag) printf("Yes\n");

	else printf("No\n");









        



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.26502603565018x):
#include<stdio.h>

int t[100010],x[100010],y[100010];

int main()

{

    int n,sum=0;

    scanf("%d",&n);

    for(int i=1;i<=n;i++)

        scanf("%d%d%d",&t[i],&x[i],&y[i]);

    for(int i=1;i<=n;i++)

    {

        sum=x[i]+y[i]-x[i-1]-y[i-1];

        if((t[i]-t[i-1])<sum)

        {

            printf("No\n");

            return 0;

        }

        if((sum-(t[i]-t[i-1]))%2)

        {

            printf("No\n");

            return 0;

        }

    }

    printf("Yes\n");

    return 0;

}
// Slower C++ solution:
#include <bits/stdc++.h>

using namespace std;



#define pb push_back

#define mp make_pair

#define f first

#define s second

#define int long long

#define double long double

typedef long long ll;

typedef pair<int,int> pii;

#define MAXN 1123456

#define INF LLONG_MAX

#define MOD 32416187567

#define cte 10002

#define MAX ULLONG_MAX



pair<int,pii> v[112345];





int32_t main(){

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.precision(11);

    cout.setf(ios::fixed);



    int n;

    cin>>n;



    for(int i=0;i<n;i++){

        cin>>v[i].f>>v[i].s.f>>v[i].s.s;

    }



    sort(v,v+n);



    int dis=abs(v[0].s.s)+abs(v[0].s.f);

    //cout<<dis<<endl;

    if(dis>v[0].f || (v[0].f-dis)%2==1){

        cout<<"No"<<endl;

        return 0;

    }





    for(int i=1;i<n;i++){

        int dis=abs(v[i].s.s-v[i-1].s.s)+abs(v[i].s.f-v[i-1].s.f);

        //cout<<dis<<endl;

        if(dis>v[i].f-v[i-1].f || ((v[i].f-v[i-1].f)-dis)%2==1){

            cout<<"No"<<endl;

            return 0;

        }

    }



    cout<<"Yes"<<endl;

    return 0;



}










// Faster C++ solution for the same problem (measured speedup: 5.368558508989576x):
#include<stdio.h>

#include<algorithm>



int main()

{

    int n,x,y,t,xx = 0,yy = 0,tt = 0,flag = 1;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d%d",&t,&x,&y);

        if(abs(x-xx)+abs(y-yy)>(t-tt) || (abs(x-xx)+abs(y-yy))%2 != (t-tt)%2)

            flag = 0;

        xx = x;

        yy = y;

        tt = t;

    }

    if(flag)

        printf("Yes\n");

    else

        printf("No\n");



    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

using namespace std;



const int MAX = 112345;



struct point {

    int x, y, t;

    point(int X = 0, int Y = 0, int T = 0):

        x(X), y(Y), t(T) {}

    

    bool operator < (const point ot) const {

        return (t < ot.t);

    }

};



bool can(point cur, point targ) {

    int D = abs(cur.x - targ.x) + abs(cur.y - targ.y);

    int T = targ.t - cur.t;

    //printf("Time %d --- Dist %d\n", T, D);

    if (T >= D && ((T - D) % 2 == 0)) return true;

    return false;

}



int N;

int main() {

    point cur = point(0, 0, 0);

    scanf("%d", &N);

    for (int i = 0; i < N; i++) {

        point targ;

        scanf("%d%d%d", &targ.t, &targ.x, &targ.y);

        if (!can(cur, targ)) {

            puts("No");

            return 0;

        }

        cur = targ;

    }



    puts("Yes");

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.22593251181629x):
#include<stdio.h>

#include<algorithm>



int main()

{

    int n,x,y,t,xx = 0,yy = 0,tt = 0,flag = 1;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d%d",&t,&x,&y);

        if(abs(x-xx)+abs(y-yy)>(t-tt) || (abs(x-xx)+abs(y-yy))%2 != (t-tt)%2)

            flag = 0;

        xx = x;

        yy = y;

        tt = t;

    }

    if(flag)

        printf("Yes\n");

    else

        printf("No\n");



    return 0;

}
// Slower C++ solution:
// i will show you da wae

#include <bits/stdc++.h>

#define mp make_pair

#define pb push_back

#define fill(x,v) memset(x,v,sizeof(x))

#define FOR(i,a,b) for(int i = int(a); i < int(b); ++i)

#define trace(x) cout << #x << " = " << x << endl

#define fastio ios_base::sync_with_stdio(0);cin.tie(0)

using namespace std;

typedef long long ll;

typedef pair<int,int> ii;



int manh(int a, int b, int c, int d){

	return abs(a-c) + abs(b-d);

}



int main(){

	    

	int n,t,a,b;

	int x = 0, y = 0, prevt = 0;

	cin >> n;

	FOR(i,0,n){

		cin >> t >> a >> b;

		int dist = manh(x,y,a,b);

		int dif = t - dist - prevt;

		x = a, y = b, prevt = t;

		if(!(dif >= 0 and ((dif%2) == 0) )){

			puts("No");

			return 0;

		}

	}

	puts("Yes");

    return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.269430697290892x):
#include<stdio.h>

#include<algorithm>



int main()

{

    int n,x,y,t,xx = 0,yy = 0,tt = 0,flag = 1;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d%d",&t,&x,&y);

        if(abs(x-xx)+abs(y-yy)>(t-tt) || (abs(x-xx)+abs(y-yy))%2 != (t-tt)%2)

            flag = 0;

        xx = x;

        yy = y;

        tt = t;

    }

    if(flag)

        printf("Yes\n");

    else

        printf("No\n");



    return 0;

}
// Slower C++ solution:
#include "bits/stdc++.h"

using namespace std;



const int maxn = 1e5 + 10;



int n;

int x[maxn], y[maxn], t[maxn];



bool solve() {

	for(int i = 1; i <= n; ++i) {

		int dx = abs(x[i] - x[i - 1]);

		int dy = abs(y[i] - y[i - 1]);



		if(dx + dy > t[i] - t[i - 1]) return false;

		if(((t[i] - t[i - 1]) - (dx + dy)) % 2) return false;

	}



	return true;

}



int main() {

	cin.sync_with_stdio(false);

	

	cin >> n;

	

	for(int i = 1; i <= n; ++i)

		cin >> t[i] >> x[i] >> y[i];

	

	if(solve()) cout << "Yes\n";

	else cout << "No\n";



	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.358208224760894x):
#include<stdio.h>

#include<algorithm>



int main()

{

    int n,x,y,t,xx = 0,yy = 0,tt = 0,flag = 1;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d%d",&t,&x,&y);

        if(abs(x-xx)+abs(y-yy)>(t-tt) || (abs(x-xx)+abs(y-yy))%2 != (t-tt)%2)

            flag = 0;

        xx = x;

        yy = y;

        tt = t;

    }

    if(flag)

        printf("Yes\n");

    else

        printf("No\n");



    return 0;

}
// Slower C++ solution:
#include<bits/stdc++.h>

const long long maxn=1e4+100;

using namespace std;

long long n,m,k,t,a[maxn],x,y,xi,yi,ti;bool le;

int main()

{

    scanf("%lld",&n);

    x=y=0;

    t=0;

    for(int i=1;i<=n;++i)

    {

        scanf("%lld%lld%lld",&ti,&xi,&yi);

        if(abs(xi-x)+abs(yi-y)>ti-t)

        {

            le=1;

        }

        if(   (ti-t -  (abs(xi-x)+abs(yi-y) ))%2==1)

        {

            le=1;

        }

        t=ti;

        x=xi;

        y=yi;

    }

    if(le)

        printf("No\n");

    else

        printf("Yes\n");

    return 0;

}


// Faster C++ solution for the same problem (measured speedup: 5.269488536678328x):
#include<stdio.h>

#include<algorithm>



int main()

{

    int n,x,y,t,xx = 0,yy = 0,tt = 0,flag = 1;

    scanf("%d",&n);

    while(n--)

    {

        scanf("%d%d%d",&t,&x,&y);

        if(abs(x-xx)+abs(y-yy)>(t-tt) || (abs(x-xx)+abs(y-yy))%2 != (t-tt)%2)

            flag = 0;

        xx = x;

        yy = y;

        tt = t;

    }

    if(flag)

        printf("Yes\n");

    else

        printf("No\n");



    return 0;

}
// Slower C++ solution:
#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define pb(x) push_back(x)

#define mp(x, y) make_pair(x, y)

typedef long long ll;

typedef pair <int, int> pii;

typedef pair <long long, long long> pll;



int main() {

	int n, x, y, t, px = 0, py = 0, pt = 0, ok = 1;

	scanf("%d", &n);

	for (int i = 0; i < n && ok; i++) {

		scanf("%d %d %d", &t, &x, &y);

		int dis = abs(x-px) + abs(y-py);

		int tme = t-pt;

		if (dis > tme or dis%2 != tme%2) ok = 0;

		px = x;

		py = y;

		pt = t;

	}

	printf(ok ? "Yes\n" : "No\n");

	return 0;

}

// Faster C++ solution for the same problem (measured speedup: 5.22911809547539x):
#include <cmath>

#include <cstdio>

using std::abs;

int main(void)

{

	int x=0,y=0,nx,ny,dx,dy;

	int t=0,nt,dt,d,N;

	bool winFlag=true;

	scanf("%d",&N);

	while(N--)

	{

		scanf("%d%d%d",&nt,&nx,&ny);

		dx=abs(nx-x);

		dy=abs(ny-y);

		y=ny;

		x=nx;



		dt=nt-t;

		t=nt;



		if(dx+dy>dt ||(dx+dy)%2 !=dt%2)

		{

			winFlag=false;

		}

	

	}

	if(winFlag)

		printf("Yes\n");

	else

		printf("No\n");





}
// Slower C++ solution:
#include<iostream>

using namespace std;



main(){

  int n,s;

  while(cin>>n>>s && n){

    int r[101]={0};

    for(int i=0;i<n;i++){

      int tmp;cin>>tmp;r[tmp]++;

    }

    int ans = 0;

    for(int i=0;i<101;i++){

      if (i+i > s && r[i])ans += (r[i]*(r[i]-1))/2;

      for(int j=i+1;j<101;j++){

	if (i+j > s && r[i] && r[j])ans += r[i]*r[j];

      }

    }

    cout << ans << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.041036147032819x):
#include<cstdio>

using namespace std;



main(){

  int n,s;

  while(scanf("%d%d",&n,&s) && n){

    int r[101]={0};

    for(int i=0;i<n;i++){

      int tmp;scanf("%d",&tmp);r[tmp]++;

    }

    int ans = 0;

    for(int i=0;i<101;i++){

      if (i+i > s && r[i])ans += (r[i]*(r[i]-1))/2;

      for(int j=i+1;j<101;j++){

	if (i+j > s && r[i] && r[j])ans += r[i]*r[j];

      }

    }

    printf("%d\n",ans);

  }

}
// Slower C++ solution:
#include<iostream>

using namespace std;



main(){

  int n,s;

  while(cin>>n>>s && n){

    int r[101]={0};

    for(int i=0;i<n;i++){

      int tmp;cin>>tmp;r[tmp]++;

    }

    int ans = 0;

    for(int i=0;i<101;i++){

      if (i+i > s && r[i])ans += (r[i]*(r[i]-1))/2;

      for(int j=i+1;j<101;j++){

	if (i+j > s && r[i] && r[j])ans += r[i]*r[j];

      }

    }

    cout << ans << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.051043073878711x):
#include<cstdio>

using namespace std;



main(){

  int n,s;

  while(true){

    scanf("%d%d",&n,&s);

    if (n==0)break;

    int r[101]={0};

    for(int i=0;i<n;i++){

      int tmp;scanf("%d",&tmp);r[tmp]++;

    }

    int ans = 0;

    for(int i=0;i<101;i++){

      if (i+i > s && r[i])ans += (r[i]*(r[i]-1))/2;

      for(int j=i+1;j<101;j++){

	if (i+j > s)ans += r[i]*r[j];

      }

    }

    printf("%d\n",ans);

  }

}
// Slower C++ solution:
#include <iostream>

#include <cstdio>

#include <cmath>

#include <vector>

#include <map>

#include <stack>

#include <queue>

#include <algorithm>

#include <set>



#define FOR(i,a,b) for(int i=(a);i<(b);i++)

#define REP(i,j) FOR(i,0,j)

#define mp std::make_pair



const int INF = 1 << 24;

const int dx[8] = {0, 0, 1, -1, 1, 1, -1, -1}, dy[8] = {1, -1, 0, 0, 1, -1, 1, -1};



typedef unsigned long long ull;

typedef std::pair<int,int> P;



int main(){

    int n, S;

    int r[10000];

    while(std::cin >> n >> S, n){

        REP(i, n){

            std::cin >> r[i];

        }

        std::sort(r, r+n);

        int res = 0;

        for(int i=0;i+1<n;i++){

            auto it = std::upper_bound(r+i+1, r+n, S-r[i]);

            res += std::distance(it, r+n);

        }

        std::cout << res << std::endl;

    }

}

// Faster C++ solution for the same problem (measured speedup: 5.022652252790821x):
#include <cstdio>

#include <algorithm>

int main(){int n,S,r[10000];while(scanf("%d%d",&n,&S),n){for(int i=0;i<n;i++){scanf("%d",r+i);}std::sort(r,r+n);int res = 0;for(int i=0;i+1<n;i++){res += std::distance(std::upper_bound(r+i+1,r+n,S-r[i]),r+n);}printf("%d\n",res);}}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  int n,s;

  int r[20100];



  while(cin>>n >> s , n||s){

    for(int i=0;i<n;i++)cin >> r[i];



    sort(r,r+n);

    int ans = 0;

    for(int i=0;i<n;i++)

      ans += n - (int)(upper_bound(r+i+1,r+n,s-r[i]) - r);

    cout << ans << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.049841418067392x):
#include<cstdio>

#include<algorithm>

using namespace std;



int main(){

  int n,s,r[20200];



  while(scanf("%d%d",&n,&s),n){

    for(int i=0;i<n;i++)scanf("%d",r+i);

    sort(r,r+n);



    int ans = 0;

    for(int i=0;i<n;i++){

      ans += n - (upper_bound(r+i+1,r+n,s-r[i]) - r);

    }

    printf("%d\n",ans);

  }

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  int n,s,r[20200];



  while(cin >> n >> s,n){

    for(int i=0;i<n;i++)cin >> r[i];

    sort(r,r+n);



    int ans = 0;

    for(int i=0;i<n;i++){

      ans += n - (upper_bound(r+i+1,r+n,s-r[i]) - r);

    }

    cout << ans << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.050778742009527x):
#include<cstdio>

#include<algorithm>

using namespace std;



int main(){

  int n,s,r[20200];



  while(scanf("%d%d",&n,&s),n){

    for(int i=0;i<n;i++)scanf("%d",r+i);

    sort(r,r+n);



    int ans = 0;

    for(int i=0;i<n;i++){

      ans += n - (upper_bound(r+i+1,r+n,s-r[i]) - r);

    }

    printf("%d\n",ans);

  }

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  int n,s;

  int r[20100];



  while(cin>>n >> s , n||s){

    for(int i=0;i<n;i++)cin >> r[i];



    sort(r,r+n);

    int ans = 0;

    for(int i=0;i<n;i++)

      ans += n - (int)(upper_bound(r+i+1,r+n,s-r[i]) - r);

    cout << ans << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.050115095092902x):
#include<cstdio>

#include<algorithm>



int main(){

  int n,s,r[20200];

  while(scanf("%d%d",&n,&s),n){

    for(int i=0;i<n;i++)scanf("%d",r+i);

    std::sort(r,r+n);

    int ans = 0;

    for(int i=0;i<n;i++)ans += n - (std::upper_bound(r+i+1,r+n,s-r[i]) - r);

    printf("%d\n",ans);

  }

}
// Slower C++ solution:
#include<iostream>

#include<algorithm>

using namespace std;



int main(){

  int n,s,r[20200];



  while(cin >> n >> s,n){

    for(int i=0;i<n;i++)cin >> r[i];

    sort(r,r+n);



    int ans = 0;

    for(int i=0;i<n;i++){

      ans += n - (upper_bound(r+i+1,r+n,s-r[i]) - r);

    }

    cout << ans << endl;

  }

}

// Faster C++ solution for the same problem (measured speedup: 5.05105246983347x):
#include<cstdio>

#include<algorithm>



int main(){

  int n,s,r[20200];

  while(scanf("%d%d",&n,&s),n){

    for(int i=0;i<n;i++)scanf("%d",r+i);

    std::sort(r,r+n);

    int ans = 0;

    for(int i=0;i<n;i++)ans += n - (std::upper_bound(r+i+1,r+n,s-r[i]) - r);

    printf("%d\n",ans);

  }

}
// Slower C++ solution:
#include <cstdio>

#include <vector>

#include <algorithm>

#include <map>

#include <queue>

#include <functional>



using namespace std;



typedef long long ll;

typedef pair<ll, ll> pii;



#define fst first

#define scd second

#define PB push_back

#define rep(i,x) for(ll i=0;i<(x);++i)



const ll linf = 3e18;



struct edge {

	ll to, cost;

	edge(ll to, ll cost = linf) : to(to), cost(cost) {}

};



ll N, M, C;



ll d[100000];

vector<edge> G[100000];

map<ll, vector<ll> >  m;

bool found[100000];

map<ll, bool> used[100000];



void dijkstra(ll s)

{

	priority_queue<pii, vector<pii>, greater<pii> > q;

	fill(d, d + N, linf);

	d[s] = 0;

	q.push(pii(0, s));

	while (q.size()) {

		pii p = q.top(); q.pop();

		ll v = p.scd;

		if (d[v] < p.fst) continue;

		rep(i, G[v].size()) {

			edge e = G[v][i];

			if (d[e.to] > d[v] + e.cost) {

				d[e.to] = d[v] + e.cost;

				m[d[e.to]].PB(e.to);

				q.push(pii(d[e.to], e.to));

			}

		}

	}

}



signed main()

{

	scanf("%lld %lld %lld", &N, &M, &C);



	ll sum = 0;



	rep(i, M) {

		ll A, B, D; scanf("%lld %lld %lld", &A, &B, &D), A--, B--;

		G[A].PB(edge(B, D));

		G[B].PB(edge(A, D));

		sum += D;

	}



	dijkstra(0);

	found[0] = true;



	ll mi = linf;



	m[0] = vector<ll>();



	for (map<ll, vector<ll> >::iterator itr = m.begin(); itr != m.end(); ++itr) {

		ll X = itr->fst;

		vector<ll> vs = itr->scd;



		rep(i, vs.size()) found[vs[i]] = true;



		rep(i, vs.size()) {

			ll v = vs[i];

			rep(j, G[v].size()) {

				edge e = G[v][j];

				if (!found[e.to]) continue;

				if (used[v][e.to]) continue;

				used[v][e.to] = used[e.to][v] = true;

				sum -= e.cost;

			}

		}



		mi = min(mi, sum + C * X);

	}



	printf("%lld\n", mi);

}

// Faster C++ solution for the same problem (measured speedup: 2.585578799243894x):
#include <bits/stdc++.h>



using namespace std;



#define int long long



#define rep(i,x) for(int i=0;i<x;++i)



#define fst first

#define scd second





using vi=vector<int>;

using pii=pair<int,int>;

using vpii=vector<pii>;

//using data=pair<pii, int>;



const int inf = 3e18;



struct edge{int to,cost;};

vector<edge> G[100010];

int d[100010];

bool used[100010];



int n, m, c;



signed main()

{

	cin >> n >> m >> c;

	

	int sum = 0;

	

	rep(i, m) {

		int a, b, d; cin >> a >> b >> d;

		--a, --b;

		G[a].push_back(edge{b, d});

		G[b].push_back(edge{a, d});

		

		sum += d;

	}

	

	priority_queue<pii, vector<pii>, greater<pii>> q;

	q.push(pii(0, 0));

	

	fill_n(d, n+1, inf);

	d[0] = 0;

	

	int ans = inf;

	

	while (q.size()) {

		pii p = q.top(); q.pop();

		

		if (d[p.scd] == p.fst) {

			used[p.scd] = true;

			

			for (edge &e : G[p.scd]) {

				if (used[e.to]) sum -= e.cost;

			}

			

			ans = min(ans, p.fst * c + sum);

		}

		

		if (d[p.scd] < p.fst) {

			continue;

		}

		

		for (edge &e : G[p.scd]) {

			if (d[e.to] > d[p.scd] + e.cost) {

				d[e.to] = d[p.scd] + e.cost;

				q.push(pii(d[e.to], e.to));

			}

		}

	}

	

	cout << ans << endl;

}
// Slower C++ solution:
#include <cstdio>

#include <vector>

#include <algorithm>

#include <map>

#include <queue>

#include <functional>



using namespace std;



typedef long long ll;

typedef pair<int, int> pii;



#define fst first

#define scd second

#define PB push_back

#define rep(i,x) for(int i=0;i<(x);++i)



const ll inf = 3e18;



struct edge {

	int to, cost;

	edge(int to, int cost) : to(to), cost(cost) {}

};



int N, M, C;



ll d[100000];

vector<edge> G[100000];

map<ll, vector<int> >  m;

bool found[100000];

map<int, bool> used[100000];



void dijkstra(int s)

{

	priority_queue<pii, vector<pii>, greater<pii> > q;

	fill(d, d + N, inf);

	d[s] = 0;

	q.push(pii(0, s));

	while (q.size()) {

		pii p = q.top(); q.pop();

		int v = p.scd;

		if (d[v] < p.fst) continue;

		rep(i, G[v].size()) {

			edge e = G[v][i];

			if (d[e.to] > d[v] + e.cost) {

				d[e.to] = d[v] + e.cost;

				m[d[e.to]].PB(e.to);

				q.push(pii(d[e.to], e.to));

			}

		}

	}

}



signed main()

{

	scanf("%d %d %d", &N, &M, &C);



	ll sum = 0;



	rep(i, M) {

		int A, B, D; scanf("%d %d %d", &A, &B, &D), A--, B--;

		G[A].PB(edge(B, D));

		G[B].PB(edge(A, D));

		sum += D;

	}



	dijkstra(0);

	found[0] = true;



	ll mi = inf;



	m[0] = vector<int>();



	for (map<ll, vector<int> >::iterator itr = m.begin(); itr != m.end(); ++itr) {

		ll X = itr->fst;

		vector<int> vs = itr->scd;



		rep(i, vs.size()) found[vs[i]] = true;



		rep(i, vs.size()) {

			int v = vs[i];

			rep(j, G[v].size()) {

				edge e = G[v][j];

				if (!found[e.to]) continue;

				if (used[v][e.to]) continue;

				used[v][e.to] = used[e.to][v] = true;

				sum -= e.cost;

			}

		}



		mi = min(mi, sum + C * X);

	}



	printf("%lld\n", mi);

}

// Faster C++ solution for the same problem (measured speedup: 2.586254244029511x):
#include <bits/stdc++.h>



using namespace std;



#define int long long



#define rep(i,x) for(int i=0;i<x;++i)



#define fst first

#define scd second





using vi=vector<int>;

using pii=pair<int,int>;

using vpii=vector<pii>;

//using data=pair<pii, int>;



const int inf = 3e18;



struct edge{int to,cost;};

vector<edge> G[100010];

int d[100010];

bool used[100010];



int n, m, c;



signed main()

{

	cin >> n >> m >> c;

	

	int sum = 0;

	

	rep(i, m) {

		int a, b, d; cin >> a >> b >> d;

		--a, --b;

		G[a].push_back(edge{b, d});

		G[b].push_back(edge{a, d});

		

		sum += d;

	}

	

	priority_queue<pii, vector<pii>, greater<pii>> q;

	q.push(pii(0, 0));

	

	fill_n(d, n+1, inf);

	d[0] = 0;

	

	int ans = inf;

	

	while (q.size()) {

		pii p = q.top(); q.pop();

		

		if (d[p.scd] == p.fst) {

			used[p.scd] = true;

			

			for (edge &e : G[p.scd]) {

				if (used[e.to]) sum -= e.cost;

			}

			

			ans = min(ans, p.fst * c + sum);

		}

		

		if (d[p.scd] < p.fst) {

			continue;

		}

		

		for (edge &e : G[p.scd]) {

			if (d[e.to] > d[p.scd] + e.cost) {

				d[e.to] = d[p.scd] + e.cost;

				q.push(pii(d[e.to], e.to));

			}

		}

	}

	

	cout << ans << endl;

}