stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

#define ll long long

#define ull unsigned long long

#define pii pair<int,int>

#define pil pair<int,along long>

#define pli pair<long long,int>

#define pll pair<long long,long long>

#define pb push_back

#define mk make_pair

#define maxn 100009

#define eps 1e-12

using namespace std;

int main()

{

	ios_base::sync_with_stdio(false);

	ll n,x;

	cin>>n>>x;

	ll base=n;

	ll repeat=n-x;

	ll ans=x;

	if(base%repeat==0)

	{

		ans+=((base/repeat)-1)*2*repeat;

		cout<<ans<<"\n";

		return 0;

	}

	if(base%repeat!=0)

	{

		ans+=(((base/repeat)*2*repeat)-repeat);

		ll temp=base;

		base=repeat;

		repeat=temp%repeat;

	}

	while(base%repeat!=0)

	{

		ans+=((base/repeat)*2*repeat);

		ll temp=base;

		base=repeat;

		repeat=temp%repeat;

	}

	ans+=((base/repeat)*2*repeat);

	ans-=repeat;

	cout<<ans<<"\n";

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll gcd(ll x,ll y){

    if(!y)

        return x;

    return gcd(y,x%y);

}

ll n,m;

int main()

{

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

   // freopen("light.out","w",stdout);

    scanf("%lld%lld",&n,&m);

    ll k=n-gcd(n,m);

    printf("%lld\n",k*3);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>



using namespace std;



using ll = long long;

using db = double;

using vi = vector<int>;

#define pb push_back

#define fir first

#define sec second



ll n, x; 



ll solve(ll n, ll x) {

	if (x * 2 == n) return 2 * x; 

	ll t = n-x; 

	ll s = (x-1) / t; 

	if (s == 0) return solve(n-x, n-2*x)+n; 

	else return solve(n-s*t, x-s*t)+2*s*t; 

}



int main() {

	cin>>n>>x; 

	cout<<solve(n,x)+x<<endl; 

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

typedef long long ll;

ll gcd(ll x,ll y){

    if(!y)

        return x;

    return gcd(y,x%y);

}

ll n,m;

int main()

{

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

   // freopen("light.out","w",stdout);

    scanf("%lld%lld",&n,&m);

    ll k=n-gcd(n,m);

    printf("%lld\n",k*3);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>



using namespace std;



typedef long long i64;



i64 gcd(i64, i64);



int main(void) {

    i64 N, X;

    cin >> N >> X;



    i64 L=N;

    i64 tmp;

    N -= X;

    if (X > N) swap(N, X);

    while (X) {

        if (N % X > 0) {

            L += 2 * (N / X) * X;

        } else {

            L += 2 * (N / X) * X - X;

            break;

        }



        tmp = X;

        X = N % X;

        N = tmp;

    }



    cout << L << endl;

    return 0;

}





i64 gcd(i64 m, i64 n) {

    i64 tmp;

    while (n) {

        if (m >= n) {

            tmp = m % n;

        } else {

            tmp = m;

        }

        m = n;

        n = tmp;

    }

    return m;

}


// Optimized solution to the same problem (faster):
#include <cstdio>

#include <algorithm>

#include <cstdint>



using namespace std;



int main() {

    int64_t N, X;

    scanf("%lld %lld", &N, &X);



    int64_t res=N;

    N -= X;

    if (N < X) swap(N, X);



    while (X) {

        res += 2*(N/X)*X;



        if (N % X == 0) {

            res -= X;

            break;

        }



        swap(N%=X, X);

    }



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

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <algorithm>

using namespace std;

long long n , x;



int main(){

  cin >> n >> x;

  cout << 3 * (n - __gcd(n , x)) << endl;

  return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

#include<algorithm>

using namespace std;

int main()

{

	long long n,x,ans;

	scanf("%lld%lld",&n,&x);

	n-=x;

//	if(x<n)

//	{

		ans=x+n;

		while(x)

		{

			ans+=(n/x*x)<<1;

			n%=x;

			swap(n,x);

		}

		ans-=n;

//	}

//	else

//	{

//		ans=x+n;

//		while(x%n)

//		{

//			ans+=(x/n*n)<<1;

//			x%=n;

//			swap(n,x);

//		}

//		ans-=n;

//	}

	

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

}

/*

5 2

*/


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <bits/stdc++.h>





using namespace std;











int main()

{

    long long a,b,mi=0,mm=0,c=0;

    cin>>a>>b;

    c=a;

    mi=min(b,a-b);

    mm=max(b,a-b);

    while(true)

    {

        if(mm%mi==0)

        {

            c+=(mm/mi)*2*mi;

            c-=mi;

            break;

        }

        else

        {

            c+=(mm/mi)*mi*2;



            mm=mm%mi;

            swap(mm,mi);





        }

    }



    cout<<c<<"\n";















    return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>



long long Solve(long long a,long long b){

    if(b%a==0)

        return b/a*a*2-a;

    return b/a*a*2+Solve(b%a,a);

}



int main(){

    long long N,X;

    scanf("%lld%lld",&N,&X);

    printf("%lld",N+Solve(X,N-X));

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



using VS = vector<string>;    using LL = long long;

using VI = vector<int>;       using VVI = vector<VI>;

using PII = pair<int, int>;   using PLL = pair<LL, LL>;

using VL = vector<LL>;        using VVL = vector<VL>;



#define ALL(a)  begin((a)),end((a))

#define RALL(a) (a).rbegin(), (a).rend()

#define PB push_back

#define EB emplace_back

#define MP make_pair

#define SZ(a) int((a).size())

#define SORT(c) sort(ALL((c)))

#define RSORT(c) sort(RALL((c)))

#define UNIQ(c) (c).erase(unique(ALL((c))), end((c)))

#define FOR(i, s, e) for (int(i) = (s); (i) < (e); (i)++)

#define FORR(i, s, e) for (int(i) = (s); (i) > (e); (i)--)

#define debug(x) cerr << #x << ": " << x << endl

const int INF = 1e9;                          const LL LINF = 1e16;

const LL MOD = 1000000007;                    const double PI = acos(-1.0);

int DX[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };    int DY[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };



/* -----  2018/03/02  Problem: 001_agc_b / Link: https://agc001.contest.atcoder.jp/tasks/agc001_b?lang=en  ----- */

/* ------問題------



高橋君は 1 辺の長さが N の 3 枚の鏡を正三角形状に組み合わせました。 三角形の頂点をそれぞれ a,b,c とします。

高橋君は、辺 ab 上の頂点 a から X の点から、辺 bc と平行に不思議な光を発射しました。 不思議な光は、普通の光と同じように真っすぐ進み、鏡に当たると反射するのですが、不思議な光がすでに通った点に当たったときにも反射をします。 例えば、N=5,X=2 のとき、不思議な光の軌跡は図の黄色い矢印のようになります。

このように不思議な光を発射した時、不思議な光は必ず発射した点に戻ってくることが証明できます。 このとき、光の軌跡の長さが全体でいくらになるかを求めて下さい。



-----問題ここまで----- */

/* -----解説等-----



あまりに対して愚直にシュミレーションをしていく

GCDっぽい…



解説↓

また，光の軌跡が三角形の集合となり，三角形の辺の長さの和が下図より N −

gcd(N, X) となることに気付くと，答えが 3(N −gcd(N, X)) であることがわかる．(らしい)



----解説ここまで---- */



LL N, X;



LL ans = 0LL;



LL f(LL x, LL n) {

	if (x == 0 || n == 0)return -(x + n);

	if (x > n)return f(n, x);

	LL c = n / x;

	return 2 * c*x + f(x, n - c*x);

}



int main() {

	cin.tie(0);

	ios_base::sync_with_stdio(false);



	cin >> N >> X;

	ans = N + f(X, N - X);



	cout << ans << "\n";



	return 0;

}


// Optimized solution to the same problem (faster):
#include<cstdio>



long long Solve(long long a,long long b){

    if(b%a==0)

        return b/a*a*2-a;

    return b/a*a*2+Solve(b%a,a);

}



int main(){

    long long N,X;

    scanf("%lld%lld",&N,&X);

    printf("%lld",N+Solve(X,N-X));

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<cstdio>

#include<iostream>

#include<cstring>

#define RG register

#define ll long long 

using namespace std;

ll n,x,y,ans;

inline ll mx(ll a,ll b){return a>b ? a : b;}

int main()

{

//	freopen("Mysterious Light.in","r",stdin);

	//freopen(".out","w",stdout);

	scanf("%lld%lld",&n,&x);

	y=mx(x,n-x); x=n-y;

	ans=n;

	while(x>=1)

	{

		if(y%x==0) { ans+=(y/x*2*x-x); break; }

		ans+=y/x*2*x;

		ll tt=x; x=y%x; y=tt;

	}

	printf("%lld",ans);

	//fclose(stdin); fclose(stdout);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>



long long Solve(long long a,long long b){

    if(b%a==0)

        return b/a*a*2-a;

    return b/a*a*2+Solve(b%a,a);

}



int main(){

    long long N,X;

    scanf("%lld%lld",&N,&X);

    printf("%lld",N+Solve(X,N-X));

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<vector>

#include<queue>

#include<utility>

#include<algorithm>

#include<cstring>

#define INF 1000000000

#define pb push_back

#define mp make_pair 

using namespace std;

typedef struct e{

  int to,cost;

}edge;

vector<vector<edge> >E(100010);

int d[100010];

void dijkstra(int s){

  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;

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

    d[i]=INF;

  d[s] = 0;

  que.push(pair<int,int>(0,s));

  while(!que.empty()){

    pair<int,int> p=que.top();que.pop();

    int v = p.second;

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

    for(int j=0;j<E[v].size();j++){

      edge t = E[v][j];

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

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

	que.push(pair<int,int>(d[t.to],t.to));

      }

    }

  }

}

int main(){

  int v,e,r;

  cin>>v>>e>>r;

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

    edge ed;

    int a,b,c;

    cin>>a>>b>>c;

    ed.to=b;ed.cost=c;

    E[a].push_back(ed);

  }

  dijkstra(r);

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

    if(d[i]==INF)

      cout<<"INF"<<endl;

    else 

      cout<<d[i]<<endl;

  }

  return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define INF 1e9

#define llINF 1e18

#define MOD 1000000007

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long

#define vi vector<ll>

#define vvi vector<vi>

#define BITLE(n) (1LL<<((ll)n))

#define SHIFT_LEFT(n) (1LL<<((ll)n))

#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))

#define ALL(a) (a).begin(),(a).end()



template<typename T>

struct Dijkstra{

  struct edge{

    int to;

    T cost;

  };

  int V;

  std::vector<std::vector<edge>>Edges;

  const T Inf = 1e9;



  Dijkstra(int V):V(V),Edges(V){}



  void add_edge(int from, int to, T cost){

    Edges[from].push_back({to, cost});

  }

  

  std::vector<T> execution(int s){

    std::vector<T> dist(V,Inf);

    std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<>>que;

    dist[s] = 0;

    que.push(std::make_pair(0, s));

    while(!que.empty()){

      int v = que.top().second;

      T cost = que.top().first;

      que.pop();

      if(dist[v] < cost)continue;

      for(auto e:Edges[v]){

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

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

	  que.push(std::make_pair(dist[e.to], e.to));

	}

      }

    }

    return dist;

  }

};



int main(){

  std::cin.tie(0);

  std::ios::sync_with_stdio(false);

  ll v,e,r;std::cin>>v>>e>>r;

  Dijkstra<int>dijkstra(v);

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

    ll a,b,c;std::cin>>a>>b>>c;

    dijkstra.add_edge(a,b,c);

  }

  for(auto e:dijkstra.execution(r)){

    if(e == INF)std::cout<<"INF"<<std::endl;

    else std::cout<<e<<std::endl;

    // std::cout<<((e == INF)?e:"INF")<<std::endl;

  }

  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

#include<string>

#include<vector>

#include<utility>

#include<queue>

#include<algorithm>

#include<cmath>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<complex>

#define INF 2147483647

#define llINF 9223372036854775807

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long



using namespace std;

typedef struct E{

  int to,cost;

}edge;

const int MAX_V=200100;

const int Inf=1e9;

vector<vector<edge> >E(MAX_V);

int d[MAX_V];

void dijkstra(int s){

  priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >que;

  fill_n(d,MAX_V,Inf);

  d[s] = 0;

  que.push(pair<int,int>(0,s));

  while(!que.empty()){

    pair<int,int> p=que.top();que.pop();

    int v = p.second;

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

    for(int j=0;j<E[v].size();j++){

      edge t = E[v][j];

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

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

	que.push(pair<int,int>(d[t.to],t.to));

      }

    }

  }

}

int main(){

  int a,b,r;cin>>a>>b>>r;

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

    edge e;

    int s;cin>>s>>e.to>>e.cost;

    E[s].pb(e);

  }

  dijkstra(r);

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

    if(d[i]==Inf)cout<<"INF"<<endl;

    else

      cout<<d[i]<<endl;

  }

  return 0;

}




// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define INF 1e9

#define llINF 1e18

#define MOD 1000000007

#define pb push_back

#define mp make_pair 

#define F first

#define S second

#define ll long long

#define vi vector<ll>

#define vvi vector<vi>

#define BITLE(n) (1LL<<((ll)n))

#define SHIFT_LEFT(n) (1LL<<((ll)n))

#define SUBS(s,f,t) ((s).substr((f),(t)-(f)))

#define ALL(a) (a).begin(),(a).end()



template<typename T>

struct Dijkstra{

  struct edge{

    int to;

    T cost;

  };

  int V;

  std::vector<std::vector<edge>>Edges;

  const T Inf = 1e9;



  Dijkstra(int V):V(V),Edges(V){}



  void add_edge(int from, int to, T cost){

    Edges[from].push_back({to, cost});

  }

  

  std::vector<T> execution(int s){

    std::vector<T> dist(V,Inf);

    std::priority_queue<std::pair<T,int>,std::vector<std::pair<T,int>>,std::greater<>>que;

    dist[s] = 0;

    que.push(std::make_pair(0, s));

    while(!que.empty()){

      int v = que.top().second;

      T cost = que.top().first;

      que.pop();

      if(dist[v] < cost)continue;

      for(auto e:Edges[v]){

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

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

	  que.push(std::make_pair(dist[e.to], e.to));

	}

      }

    }

    return dist;

  }

};



int main(){

  std::cin.tie(0);

  std::ios::sync_with_stdio(false);

  ll v,e,r;std::cin>>v>>e>>r;

  Dijkstra<int>dijkstra(v);

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

    ll a,b,c;std::cin>>a>>b>>c;

    dijkstra.add_edge(a,b,c);

  }

  for(auto e:dijkstra.execution(r)){

    if(e == INF)std::cout<<"INF"<<std::endl;

    else std::cout<<e<<std::endl;

    // std::cout<<((e == INF)?e:"INF")<<std::endl;

  }

  return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define F first

#define S second

#define PB push_back

using namespace std;

typedef pair<int,int>P;

typedef vector<P>VP;

typedef vector<int>V;

V town[100001],cost[100001];

int d[100001];

bool flg[100001];

int main(void){

	int n,m,s;

	int f,t,c;

	int i,j;

	

	priority_queue<P,VP,greater<P> >que;

	P pp;

	int x,y;

	int b,bc;

	

	cin>>n>>m>>s;

	for(i=0;i<m;i++){

		cin>>f>>t>>c;

		town[f].PB(t);

		cost[f].PB(c);

	}

	

	fill(d,d+n,INT_MAX);

	fill(flg,flg+n,false);

	

	

	que.push(make_pair(0,s));

	while(!que.empty()){

		pp=que.top();	que.pop();

		x=pp.F;	y=pp.S;

		if(!flg[y]){

			d[y]=x;

			flg[y]=true;

			for(i=0;i<town[y].size();i++){

				b=town[y][i];

				bc=cost[y][i];

				if(!flg[b]){

					que.push(make_pair(x+bc,b));

				}

			}

		}

	}

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

		if(d[i]==INT_MAX)	cout<<"INF"<<endl;

		else				cout<<d[i]<<endl;

	}

	return 0;

}

	

	


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define F first

#define S second

#define PB push_back

using namespace std;

typedef pair<int,int>P;

typedef vector<P>VP;

typedef priority_queue<P,VP,greater<P>>PQ;

int flg[100000],d[100000];

VP v[100000];

int main(void){

	int n,m,s;

	int x,y,cost;

	int now,next;

	int now_cost,next_cost;

	int i,j;

	int flag;

	P pp;

	PQ que;

	cin>>n>>m>>s;

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

		flg[i]=0;

		d[i]=INT_MAX;

	}

	for(i=0;i<m;i++){

		cin>>x>>y>>cost;

		v[x].PB(P(cost,y));

	}

	que.push(P(0,s));

	while(!que.empty()){

		pp=que.top();

		que.pop();

		now_cost=pp.F;

		now=pp.S;

		if(flg[now]==0){

			flg[now]=1;

			d[now]=now_cost;

			for(i=0;i<(int)v[now].size();i++){

				next_cost=v[now][i].F;

				next=v[now][i].S;

				if(flg[next]==0)	que.push(P(now_cost+next_cost,next));

			}

		}

	}

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

		if(d[i]==INT_MAX)	cout<<"INF"<<endl;

		else				cout<<d[i]<<endl;

	}

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#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;

 

typedef pair<int,int> ii;

const int IINF = INT_MAX;

 

vector<ii> G[100010];

int mincost[100010];

int V,E,r;

 

int main(){

  scanf("%d %d %d",&V,&E,&r);

 

  int s,t,d;

  rep(i,E){

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

    G[s].push_back(ii(t,d));

  }

 

  rep(i,V) mincost[i] = IINF;

  mincost[r] = 0;

  deque<int> deq; deq.push_back(r);

  vector<int> in_queue(V,0); in_queue[r] = 1;

 

  while(!deq.empty()){

    int u = deq.front(); deq.pop_front(); in_queue[u] = 0;

    rep(i,(int)G[u].size()){

      int v = G[u][i].first, c = G[u][i].second;

      if( mincost[v] > mincost[u] + c ) {

        mincost[v] = mincost[u] + c;

        if( !in_queue[v] ) {

          deq.push_back(v);

          in_queue[v] = 1;

        }

      }

    }

  }

 

  rep(i,V) {

    if( mincost[i] == IINF ) puts("INF");

    else printf("%d\n",mincost[i]);

  }

 

  return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <vector>

#include <cmath>

#include <algorithm>

using namespace std;

#define INF (2e9)

const int maxv=100000+10;

const int maxe=500000+10;

int V,E,S;

struct Edge{int from, to,cost;};

int d[maxv];

Edge es[maxe];

 

void bellman_ford(int s)

{

    for(int i=0;i<V;i++) d[i]=INF;

    bool bUpdate=true;

    d[s]=0;

    while(true)

    {

        bUpdate=false;

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

        {

            Edge &e=es[i];

            if(d[e.from]!=INF&&d[e.to]>d[e.from]+e.cost)

            {

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

                bUpdate=true;

            }

        }

        if(!bUpdate) break;

    }

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

    {

        if(d[i]!=INF)  printf("%d\n",d[i]);

        else printf("INF\n");

 

 

    }

}

int main()

{

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

//    freopen("out.txt","w",stdout);

    scanf("%d%d%d",&V,&E,&S);

    int u,v,dd;

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

    {

        scanf("%d%d%d",&u,&v,&dd);

        es[i].from=u;

        es[i].to=v;

        es[i].cost=dd;

    }

    bellman_ford(S);

 

    return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define MAX 200010

#define inf 1<<30

#define linf 1e16

#define eps (1e-8)

#define mod 1000000007

#define pi acos(-1)

#define phi (1.0+sqrt(5))/2.0

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define all(a) (a).begin(),(a).end()

#define pd(a) printf("%.10f\n",(double)(a))

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

#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)

#define equals(a,b) (fabs((a)-(b))<eps)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<int,double> pid;

typedef pair<double,int> pdi;

typedef vector<int> vi;

typedef vector<pii> vpi;

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

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



int v,e,r;

vector<pii> g[MAX];



void dijkstra(){

  int d[MAX];

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

  fill(d,d+MAX,inf);

  d[r]=0;

  pq.push(mp(0,r));



  while(pq.size()){

    pii u=pq.top();

    pq.pop();

    if(d[u.s]<u.f)continue;



    FOR(i,0,g[u.s].size()){

      int next=g[u.s][i].f;

      int cost=d[u.s]+g[u.s][i].s;

      if(cost<d[next]){

        d[next]=cost;

        pq.push(mp(cost,next));

      }

    }

  }

  FOR(i,0,v){

    if(d[i]==inf)cout<<"INF"<<endl;

    else cout<<d[i]<<endl;

  }

  return;

}



int main()

{

  cin>>v>>e>>r;

  FOR(i,0,e){

    int a,b,c;

    cin>>a>>b>>c;

    g[a].pb(mp(b,c));

  }

  dijkstra();

  return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

#define MAX 100010

#define inf 1<<30

#define linf 1e16

#define eps (1e-8)

#define mod 1000000007

#define pi acos(-1)

#define phi (1.0+sqrt(5))/2.0

#define f first

#define s second

#define mp make_pair

#define pb push_back

#define all(a) (a).begin(),(a).end()

#define pd(a) printf("%.10f\n",(double)(a))

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

#define RFOR(i,a,b) for(int i=(a)-1;(b)<=i;i--)

#define equals(a,b) (fabs((a)-(b))<eps)

using namespace std;

typedef long long ll;

typedef unsigned long long ull;

typedef pair<int,int> pii;

typedef pair<int,double> pid;

typedef pair<double,int> pdi;

typedef vector<int> vi;

typedef vector<pii> vpi;

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

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



int v,e,r;

vector<pii> g[MAX];



void dijkstra(){

  int d[MAX];

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

  fill(d,d+MAX,inf);

  d[r]=0;

  pq.push(mp(0,r));



  while(pq.size()){

    pii u=pq.top();

    pq.pop();

    if(d[u.s]<u.f)continue;



    FOR(i,0,g[u.s].size()){

      int next=g[u.s][i].f;

      int cost=d[u.s]+g[u.s][i].s;

      if(cost<d[next]){

        d[next]=cost;

        pq.push(mp(cost,next));

      }

    }

  }

  FOR(i,0,v){

    if(d[i]==inf)printf("INF\n");

    else printf("%d\n",d[i]);

  }

  return;

}



int main()

{

  scanf("%d%d%d",&v,&e,&r);

  FOR(i,0,e){

    int a,b,c;

    scanf("%d%d%d",&a,&b,&c);

    g[a].pb(mp(b,c));

  }

  dijkstra();

  return 0;

}

// Fastest known solution for this problem: