stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 100010

char ss[maxn];

int main()

{

	int n;

	cin>>n;

	cin>>ss;

	int siz=sizeof(ss);

	char pre;

	pre=ss[0];

	int cnt=0;

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

	{

		if(pre!=ss[i])

		{

			cnt++;

			pre=ss[i];

		 } 

	}

	cout<<cnt;

	return 0;

 } 

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

using namespace std;

typedef long long ll;

#define fast ios_base::sync_with_stdio(false) , cin.tie(0) ;

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

#define w(x) cout << (#x) << " is " << x << "\n" ;



int main()

{

    fast ;

    int n,c=0,i;

    string s ;

    cin >> n >> s ;

    for(i= 0 ; i < n-1 ; i++)

    {

        if(s[i]!=s[i+1])

            c++;

    }

    cout << c+1 << "\n";

    return 0;

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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 100010

char ss[maxn];

int main()

{

	int n;

	cin>>n;

	cin>>ss;

	int siz=sizeof(ss);

	char pre;

	pre=ss[0];

	int cnt=0;

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

	{

		if(pre!=ss[i])

		{

			cnt++;

			pre=ss[i];

		 } 

	}

	cout<<cnt;

	return 0;

 } 

// Faster C++ solution for the same problem (measured speedup: 1.2476068702182561x):


#include<bits/stdc++.h>

using namespace std;

int main()

{

    long long a,b,c,d=0,e,f,g,h,i,j,k,l,m,n,x,y,z;

    cin>>a;

    char ch,dh;

    cin>>ch;



    for(i=1;i<a;i++)

    {



    cin>>dh;

    if(dh!=ch)

    {

        d++;

        ch=dh;

    }



    }

    cout<<d+1<<endl;















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

#include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

#define maxn 100010

char ss[maxn];

int main()

{

	int n;

	cin>>n;

	cin>>ss;

	int siz=sizeof(ss);

	char pre;

	pre=ss[0];

	int cnt=0;

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

	{

		if(pre!=ss[i])

		{

			cnt++;

			pre=ss[i];

		 } 

	}

	cout<<cnt;

	return 0;

 } 

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

using namespace std;

#define int  long long

#define tc(t)  int t; cin>>t; while(t--)

#define f(n)    for(int i=0;i<n;i++)

#define endl   "\n"

int32_t main() {

    ios_base::sync_with_stdio(false);

    cin.tie(NULL);



    int n;

    cin>>n;

    string slim;

    cin>>slim;

    int count=0;

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

    {

        if(i==0) {

            count++;

            continue;



        }

        if(slim[i]==slim[i-1]) continue;

        else count++;





    }

    cout<<count<<endl;











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

using namespace std;



int main(){

	int n;

	scanf("%d",&n);

	string str;

	cin>>str;

	string s="";

	for(int i=0;i<str.length();i++){

		if(s=="") s+=str[i];

		else{

			if(s[s.length()-1]!=str[i]){

				s+=str[i];

			}

		}

	}

	cout<<s.size()<<endl;

}


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

int n,ans;

char ch1,ch2;

int main()

{

	scanf("%d",&n);

	ch1=getchar();

	ch1=getchar();

	ans=1;

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

	{

	    ch2=getchar();

	    if(ch2!=ch1) ans++;

	    ch1=ch2;

	}

	printf("%d",ans);

}
// Slower C++ solution:
//p1t3

//P1T2

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e4;

int raw[maxn];

int main(){

	int n;

	cin >> n;

	string s;

	cin >> s;

	char pre = s[0];

	int ans = 1;

	for(int i = 1;i < s.size();i++){

		if(s[i] != pre){

			ans++;

			pre = s[i];

		}

	}

	printf("%d",ans);

	return 0;

}

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

int n,ans;

char ch1,ch2;

int main()

{

	scanf("%d",&n);

	ch1=getchar();

	ch1=getchar();

	ans=1;

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

	{

	    ch2=getchar();

	    if(ch2!=ch1) ans++;

	    ch1=ch2;

	}

	printf("%d",ans);

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

#include <stack>

using namespace std;



stack<char> s;



int main() {

    int n;

    cin >> n;

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

        char t;

        cin >> t;

        if (s.empty())

            s.push(t);

        else if (t == s.top())

            ;

        else

            s.push(t);

    }



    cout << s.size();



    return 0;

}

// Created by Kevin Weng on 2019/10/28.

//




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

int n,ans;

char ch1,ch2;

int main()

{

	scanf("%d",&n);

	ch1=getchar();

	ch1=getchar();

	ans=1;

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

	{

	    ch2=getchar();

	    if(ch2!=ch1) ans++;

	    ch1=ch2;

	}

	printf("%d",ans);

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

using namespace std;

int main(){

	int w;

	cin>>w;

	string s;

	cin>>s;

	int ans=1;

	int n=s.size();

	char q=s[0];

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

	{

		if(s[i]!=q)

		{

			ans++;

			q=s[i];

		}

	}

	cout<<ans;

	return 0;

}


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

const int maxn = 100010;

int main()

{

    int n;

    char p[maxn];

    scanf("%d", &n);

    scanf("%s", p);

    char c = p[0];

    int num = 1;

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

        if(p[i] != c){

            num++;

            c = p[i];

        }

    }

    printf("%d", num);

    return 0;

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

using namespace std;



int cut;

int n;

char s[100010];

int main(){

	scanf("%d",&n);

	scanf("%s",s+1);

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

    	if(s[i]==s[i-1]){

    		cut++;

		}

	}

	printf("%d",n-cut);

	return 0;

}

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

const int maxn = 100010;

int main()

{

    int n;

    char p[maxn];

    scanf("%d", &n);

    scanf("%s", p);

    char c = p[0];

    int num = 1;

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

        if(p[i] != c){

            num++;

            c = p[i];

        }

    }

    printf("%d", num);

    return 0;

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

#include <cstdio>

#include <string>

using namespace std;

int main()

{

	int N;

	string s;

	int ans = 1;

	cin>>N;

	getchar();

	getline(cin, s);

	char f = s[0];

	for(int i =1;i<s.length();i++)

	{

		if(f==s[i])

			continue;

		else

		{

			ans++;

			f=s[i];

		}

	}

	cout<<ans<<endl;

	return 0;

}

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

const int maxn = 100010;

int main()

{

    int n;

    char p[maxn];

    scanf("%d", &n);

    scanf("%s", p);

    char c = p[0];

    int num = 1;

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

        if(p[i] != c){

            num++;

            c = p[i];

        }

    }

    printf("%d", num);

    return 0;

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

using namespace std;

char a , b;

int n, countor = 0;

int main(){

    cin >> n;

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

        cin >> b;

        if(b!=a){

            countor++;

            a = b;

        }

    }

    cout << countor;

    return 0;

}

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

const int maxn = 100010;

int main()

{

    int n;

    char p[maxn];

    scanf("%d", &n);

    scanf("%s", p);

    char c = p[0];

    int num = 1;

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

        if(p[i] != c){

            num++;

            c = p[i];

        }

    }

    printf("%d", num);

    return 0;

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

#include<string>

using namespace std;

int main()

{

	int n;

	char str[100005];

	int c[100005];

	cin>>n;

	cin>>str;

	int i,j,z=n;

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

	{

		c[i]=str[i]-'0';

	}

	for(i=0;i<n-1;i++)

	{

		if(c[i]==c[i+1])

		{

			z--;

		}

	}

	cout<<z<<endl;

}

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

const int maxn = 100010;

int main()

{

    int n;

    char p[maxn];

    scanf("%d", &n);

    scanf("%s", p);

    char c = p[0];

    int num = 1;

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

        if(p[i] != c){

            num++;

            c = p[i];

        }

    }

    printf("%d", num);

    return 0;

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

#define ll long long

using namespace std;

ll n , x;

ll f(ll x , ll y)//x < y

{

	//cout << x << " " << y << endl;

	if(!(y % x))

	{

		ll step = y / x;

		return 2 * step * x - x;

	}



	if(x == y)

		return y;

	ll step = y / x;

	return 2 * step * x + f(min(x , y - step * x) , max(y - step * x , x));

}



int main()

{

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

	cin >> n >> x;

	ll ans = n;

	ans += f(min(x , n - x) , max(x, n - x));

	cout << ans;

}




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

#include <cstring>

#include <cstdio>



#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)



using namespace std;

typedef long long i64;



i64 N, K;



i64 simulate(i64 x, i64 y)

{

	if(y == 0)

		return (-x);

	return simulate(y, x % y) + 2 * (x / y) * y;

}



int main()

{

	//REDIRECT("light");



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

	printf("%lld\n", simulate(max(K, N - K), min(K, N - K)) + N);



	CLOSEALL();

	return 0;

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



using namespace std;



//#define _FILES

#define PB push_back

#define MP make_pair

#define X first

#define Y second



long long solve(long long n, long long x)

{

    if (((n % 2) == 0) && (x == n/2))

    {

        return 3 * (n / 2);

    }



    if (x <= n / 2)

    {

        return  3 * x + solve(n - x, n - 2 * x);

    }



    long long ans = x + 2 * (x / (n - x)) * (n - x);

    long long ost = x % (n - x);



    if (!ost)

    {

        return ans;

    }



    ans += solve(ost + n - x, ost) - ost;

    return ans;

}



int main()

{

    ios_base::sync_with_stdio(false);



    #ifdef _FILES

        freopen("","r",stdin);

        freopen("","w",stdout);

    #endif // _FILES

    long long n, x;

    cin >> n >> x;

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

    return 0;

}




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

#include <cstring>

#include <cstdio>



#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)



using namespace std;

typedef long long i64;



i64 N, K;



i64 simulate(i64 x, i64 y)

{

	if(y == 0)

		return (-x);

	return simulate(y, x % y) + 2 * (x / y) * y;

}



int main()

{

	//REDIRECT("light");



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

	printf("%lld\n", simulate(max(K, N - K), min(K, N - K)) + N);



	CLOSEALL();

	return 0;

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



#define endl '\n'



using namespace std;



typedef long long ll;



int main(){

	ios_base::sync_with_stdio(0);

	cin.tie(0);

	cout.tie(0);



	ll n, x;

	cin >> n >> x;

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

	return 0;

}

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

#include <cstring>

#include <cstdio>



#define REDIRECT(x) freopen(x".in", "r", stdin), freopen(x".out", "w", stdout)

#define CLOSEALL() fclose(stdin), fclose(stdout)



using namespace std;

typedef long long i64;



i64 N, K;



i64 simulate(i64 x, i64 y)

{

	if(y == 0)

		return (-x);

	return simulate(y, x % y) + 2 * (x / y) * y;

}



int main()

{

	//REDIRECT("light");



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

	printf("%lld\n", simulate(max(K, N - K), min(K, N - K)) + N);



	CLOSEALL();

	return 0;

}
// Slower C++ solution:
#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";

}

// Faster C++ solution for the same problem (measured speedup: 5.336647317234863x):
#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);

}
// Slower C++ solution:
#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; 

}


// Faster C++ solution for the same problem (measured speedup: 5.261389743728158x):
#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);

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.247784226248711x):
#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;

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.255921812596219x):
#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

*/
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.269350842818595x):
#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));

}
// Slower C++ solution:
#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;

}


// Faster C++ solution for the same problem (measured speedup: 5.344665591611412x):
#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));

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 5.204104670495237x):
#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));

}
// Slower C++ solution:
#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;

}

// Faster C++ solution for the same problem (measured speedup: 3.874794194575533x):
#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;

}