stablegradients/pie-gem5-bysrc huggingface dataset:
// 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()

{

  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;

}

// 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:
// Original C++ solution (slower):
#include<bits/stdc++.h>



using namespace std;



const int IINF = INT_MAX;

int V,E,r;



vector<int> G[110000];

vector<int> W[110000];

int mindist[110000];



void dijkstra(){

  for(int i=0;i<V;i++) mindist[i] = IINF;

  mindist[r] = 0;

  priority_queue<int> Q;

  Q.push(r);

  while( !Q.empty() ){

    int cur = Q.top(); Q.pop();

    for(int i=0;i<(int)G[cur].size();i++){

      int next   = G[cur][i];

      int weight = W[cur][i];

      if( mindist[next] > mindist[cur] + weight )  {

	mindist[next] = mindist[cur] + weight;

	Q.push(next);

      }

    }

  }

}



int main(){



  cin >> V >> E >> r;



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

    int s,t,d;

    cin >> s >> t >> d;

    G[s].push_back(t);

    W[s].push_back(d);

  }



  dijkstra();

  

  for(int t=0;t<V;t++) {

    if( mindist[t] != IINF ) cout << mindist[t] << endl;

    else                     cout << "INF" << endl;

  }



  return 0;

}

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



using namespace std;



struct Edge { int src,dst,weight; };



struct Data {

  int cur,weight;

  bool operator < ( const Data &data ) const {

    if( weight != data.weight ) return weight > data.weight;

    return cur > data.cur;

  }

};



const int IINF = INT_MAX;

const int MAX_V = 100010;

int V,E,mindist[MAX_V];

vector<Edge> G[MAX_V];



void dijkstra(int source){

  for(int i=0;i<V;i++) mindist[i] = IINF;

  mindist[source] = 0;

  priority_queue<Data> Q;

  Q.push((Data){source,0});

  while( !Q.empty() ){

    Data data = Q.top(); Q.pop();

    if( mindist[data.cur] < data.weight ) continue;

    for(int i=0;i<(int)G[data.cur].size();i++){

      int next = G[data.cur][i].dst;

      if( mindist[next] > data.weight + G[data.cur][i].weight ){

	mindist[next] = data.weight + G[data.cur][i].weight;

	Q.push((Data){next,mindist[next]});

      }

    }

  }

}



int main(){

  int source;

  cin >> V >> E >> source;

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

    int src,dst,weight;

    cin >> src >> dst >> weight;

    G[src].push_back((Edge){src,dst,weight});

    //G[dst].push_back((Edge){dst,src,weight}); // undirected graph

  }

  dijkstra(source);

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

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

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

  }

  return 0;

}

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



using namespace std;



struct Data {

  int cur,weight;

  bool operator < ( const Data &data ) const {

    return weight > data.weight;

  }

};



const int IINF = INT_MAX;

int V,E,r;



vector<int> G[110000];

vector<int> W[110000];

int mindist[110000];



void dijkstra(){

  for(int i=0;i<V;i++) mindist[i] = IINF;

  mindist[r] = 0;

  priority_queue<Data> Q;

  Q.push((Data){r,0});

  while( !Q.empty() ){

    Data data = Q.top(); Q.pop();

    int cur = data.cur;

    if( mindist[cur] < data.weight ) continue;

    for(int i=0;i<(int)G[cur].size();i++){

      int next   = G[cur][i];

      if( mindist[next] > data.weight + W[cur][i] )  {

	mindist[next] = data.weight + W[cur][i];

	Q.push((Data){next,mindist[next]});

      }

    }

  }

}



int main(){



  cin >> V >> E >> r;



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

    int s,t,d;

    cin >> s >> t >> d;

    G[s].push_back(t);

    W[s].push_back(d);

  }



  dijkstra();

  

  for(int t=0;t<V;t++) {

    if( mindist[t] != IINF ) cout << mindist[t] << endl;

    else                     cout << "INF" << endl;

  }



  return 0;

}

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



using namespace std;



struct Edge { int src,dst,weight; };



struct Data {

  int cur,weight;

  bool operator < ( const Data &data ) const {

    if( weight != data.weight ) return weight > data.weight;

    return cur > data.cur;

  }

};



const int IINF = INT_MAX;

const int MAX_V = 100010;

int V,E,mindist[MAX_V];

vector<Edge> G[MAX_V];



void dijkstra(int source){

  for(int i=0;i<V;i++) mindist[i] = IINF;

  mindist[source] = 0;

  priority_queue<Data> Q;

  Q.push((Data){source,0});

  while( !Q.empty() ){

    Data data = Q.top(); Q.pop();

    if( mindist[data.cur] < data.weight ) continue;

    for(int i=0;i<(int)G[data.cur].size();i++){

      int next = G[data.cur][i].dst;

      if( mindist[next] > data.weight + G[data.cur][i].weight ){

	mindist[next] = data.weight + G[data.cur][i].weight;

	Q.push((Data){next,mindist[next]});

      }

    }

  }

}



int main(){

  int source;

  cin >> V >> E >> source;

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

    int src,dst,weight;

    cin >> src >> dst >> weight;

    G[src].push_back((Edge){src,dst,weight});

    //G[dst].push_back((Edge){dst,src,weight}); // undirected graph

  }

  dijkstra(source);

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

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

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

  }

  return 0;

}

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

#include<vector>

#include<string>

#include<algorithm>

#include<map>

#include<set>

#include<utility>

#include<cmath>

#include<cstring>

#include<queue>

#include<cstdio>

#include<sstream>

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

#define rep(i,a) loop(i,0,a)

#define pb push_back

#define mp make_pair

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

const double PI=acos(-1);

const double EPS=1e-10;

const int inf=1e9;

using namespace std;

typedef long long ll;

typedef vector<int> vi;

typedef vector<vi> vvi;

typedef pair<ll,ll> pii;

#define MAX_V 100010

struct edge{

	int to,cost;

};

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

int V,E,s;

void dijkstra(){

	vi d(MAX_V);

	rep(i,MAX_V)d[i]=inf;

	d[s]=0;

	priority_queue<pii>q;

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

	while(!q.empty()){

		pii p=q.top();

		q.pop();

		int pos=p.second,cost=-p.first;

		if(cost>d[pos])continue;

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

			edge e=G[pos][i];

			int to=e.to;

			int nowcost=cost+e.cost;

			if(nowcost<d[to]){

				d[to]=nowcost;

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

			}

		}

	}

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

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

}

int main(){

	cin>>V>>E>>s;

	while(E--){

		int a,b,c;

		cin>>a>>b>>c;

		edge t={b,c};

		G[a].pb(t);

	}

	dijkstra();

}

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

#include<vector>

#include<string>

#include<algorithm>	

#include<map>

#include<set>

#include<utility>

#include<cmath>

#include<cstring>

#include<queue>

#include<cstdio>

#include<sstream>

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

#define rep(i,a) loop(i,0,a)

#define pb push_back

#define mp make_pair

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

using namespace std;

//kaewasuretyuui

typedef long long ll;

typedef pair<ll,ll> pii;

typedef vector<ll> vi;

typedef vector<vi> vvi;

typedef vector<pii> vp;

typedef vector<vp> vvp;

typedef pair<int,pii> pip;

typedef vector<pip>vip;

const double PI=acos(-1);

const double EPS=1e-8;

const ll inf=1e18;

struct edge{

	int to,cost;

};

class DIJ{

	public:

	vector<vector<edge> >G;

	int n;

	vi d;//distance

	DIJ(int size){

		n=size;

		G=vector<vector<edge> >(n);

	}

	void add_edge(int a,int b,int c){

		edge e={b,c},ee={a,c};

		G[a].pb(e);

//		G[b].pb(ee);

	}

	void dij(int s){

		d=vi(n,inf);

		d[s]=0;

		priority_queue<pii>q;

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

		while(!q.empty()){

			pii p=q.top();

			q.pop();

			int pos=p.second,cost=-p.first;

			if(cost>d[pos])continue;

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

				edge e=G[pos][i];

				int to=e.to;

				int nowcost=cost+e.cost;

				if(nowcost<d[to]){

					d[to]=nowcost;

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

				}

			}

		}

	}

};

int main(){

	int n,m,s;

	cin>>n>>m>>s;

	DIJ dij(n);

	while(m--){

		int a,b,c;

		cin>>a>>b>>c;

		dij.add_edge(a,b,c);

	}

	dij.dij(s);

	rep(i,n)if(dij.d[i]!=inf)cout<<dij.d[i]<<endl;

		else cout<<"INF"<<endl;

}

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

#include <vector>

#include <queue>

#include <functional>



using namespace std;

typedef pair<int, int> P;

static const int INF = 1e9;

static const int SIZE = 100001;

struct edge

{

	int to;

	int cost;

};



vector<edge> G[SIZE];

int d[SIZE];



void solve()

{

	int V, E, start;

	cin >> V >> E >> start;

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

	{

		int from, to, cost;

		cin >> from >> to >> cost;

		edge e;

		e.to = to;

		e.cost = cost;

		G[from].push_back(e);

	}

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

	{

		d[i] = INF;

	}

	d[start] = 0;

	priority_queue<P, vector<P>, greater<P> > pque;

	pque.push(P(0, start));

	while (!pque.empty())

	{

		P p = pque.top();

		pque.pop();

		int v = p.second;

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

		{

			edge e = G[v][i];

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

			{

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

				pque.push(P(d[e.to], e.to));

			}

		}

	}

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

	{

		if (d[i] == INF)

		{

			cout << "INF" << endl;

		}

		else

		{

			cout << d[i] << endl;

		}

	}

}



int main()

{

	solve();

	return(0);

}

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

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <cmath>



using namespace std;

typedef pair<int, int> P;

typedef pair<P, int> PI;

static const long long int INF = 1e18;



class Edge

{

public:

	int to;

	int cost;

};

vector<Edge> edge[100001];



void solve()

{

	int V, E, r;

	cin >> V >> E >> r;

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

	{

		int s, t, d;

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

		Edge e;

		e.to = t;

		e.cost = d;

		edge[s].push_back(e);

	}

	vector<long long int> D(V);

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

	{

		D[i] = INF;

	}

	D[r] = 0;

	priority_queue<P, vector<P>, greater<P> > pque;

	pque.push(P(0, r));

	while (!pque.empty())

	{

		P p = pque.top();

		pque.pop();

		int v = p.second;

		if (D[v] < p.first)

		{

			continue;

		}

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

		{

			Edge e = edge[v][i];

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

			{

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

				pque.push(P(D[e.to], e.to));

			}

		}

	}

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

	{

		if (D[i] == INF)

		{

			cout << "INF" << endl;

		}

		else

		{

			cout << D[i] << endl;

		}

	}

}



int main()

{

	solve();

	return(0);

}


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

#include <cstdio>

#include <vector>

#include <queue>

#include <functional>



using namespace std;

typedef pair<int, int> P;

static const int INF = 1e9;

static const int SIZE = 100001;

struct edge

{

	int to;

	int cost;

};



vector<edge> G[SIZE];

int d[SIZE];



void solve()

{

	int V, E, start;

	cin >> V >> E >> start;

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

	{

		int from, to, cost;

		scanf("%d %d %d", &from, &to, &cost);

//		cin >> from >> to >> cost;

		edge e;

		e.to = to;

		e.cost = cost;

		G[from].push_back(e);

	}

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

	{

		d[i] = INF;

	}

	d[start] = 0;

	priority_queue<P, vector<P>, greater<P> > pque;

	pque.push(P(0, start));

	while (!pque.empty())

	{

		P p = pque.top();

		pque.pop();

		int v = p.second;

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

		{

			edge e = G[v][i];

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

			{

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

				pque.push(P(d[e.to], e.to));

			}

		}

	}

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

	{

		if (d[i] == INF)

		{

			cout << "INF" << endl;

		}

		else

		{

			cout << d[i] << endl;

		}

	}

}



int main()

{

	solve();

	return(0);

}

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

#include <cstdio>

#include <string>

#include <vector>

#include <algorithm>

#include <set>

#include <map>

#include <queue>

#include <cmath>



using namespace std;

typedef pair<int, int> P;

typedef pair<P, int> PI;

static const long long int INF = 1e18;



class Edge

{

public:

	int to;

	int cost;

};

vector<Edge> edge[100001];



void solve()

{

	int V, E, r;

	cin >> V >> E >> r;

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

	{

		int s, t, d;

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

		Edge e;

		e.to = t;

		e.cost = d;

		edge[s].push_back(e);

	}

	vector<long long int> D(V);

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

	{

		D[i] = INF;

	}

	D[r] = 0;

	priority_queue<P, vector<P>, greater<P> > pque;

	pque.push(P(0, r));

	while (!pque.empty())

	{

		P p = pque.top();

		pque.pop();

		int v = p.second;

		if (D[v] < p.first)

		{

			continue;

		}

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

		{

			Edge e = edge[v][i];

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

			{

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

				pque.push(P(D[e.to], e.to));

			}

		}

	}

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

	{

		if (D[i] == INF)

		{

			cout << "INF" << endl;

		}

		else

		{

			cout << D[i] << endl;

		}

	}

}



int main()

{

	solve();

	return(0);

}


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

#include <vector>

#include <queue>

#include <algorithm>

#include <functional>

using namespace std;



#define MAX_V 100001

const long long INF = 1LL<<60;



static int V, E, r;

static vector<pair<int, long long> > graph[MAX_V];

static long long dist[MAX_V];



int main() {

  cin >> V >> E >> r;

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

    int s, t; long long w;

    cin >> s >> t >> w;

    graph[s].push_back(make_pair(t, w));

  }



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



  for (int i = 0; i < MAX_V; ++i) dist[i] = INF;

  dist[r] = 0;

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



  while (!que.empty()) {

    long long curDist = que.top().first;

    int curVertex = que.top().second;

    que.pop();



    if (dist[curVertex] < curDist) continue;



    for (int i = 0; i < graph[curVertex].size(); ++i) {

      int toVertex = graph[curVertex][i].first;

      long long toDist = curDist + graph[curVertex][i].second;



      if (dist[toVertex] > toDist) {

	dist[toVertex] = toDist;

	que.push(make_pair(toDist, toVertex));

      }

    }

  }



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

    if (dist[i] < INF) cout << dist[i] << endl;

    else cout << "INF" << endl;

  }

}


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

#include <vector>

#include <queue>

using namespace std;



// 無限大を表す値

const long long INF = 1LL<<60;



// 辺を表す型，ここでは重みを表す型を long long 型とします

struct Edge {

    int to; // 隣接頂点番号

    long long w; // 重み

    Edge(int to, long long w) : to(to), w(w) {}

};



// 重み付きグラフを表す型，各頂点の隣接リストを辺集合で表す

typedef vector<vector<Edge> > Graph;



// 緩和処理 (更新が行われたときは true を返し，行われないときは false を返す)

bool chmin(long long& a, long long b) {

    if (a > b) {

        a = b;

        return true;

    }

    else return false;

}



int main() {

    // 頂点数と辺数，始点

    int N, M, s; cin >> N >> M >> s;



    // グラフ

    Graph G(N);

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

        int a, b, w;

        cin >> a >> b >> w;

        G[a].push_back(Edge(b, w));

    }



    // Dijkstra 法

    vector<long long> dist(N, INF);

    dist[s] = 0;



    // (d[v], v) のペアを要素としたヒープを作ります

    priority_queue<pair<long long, int>,

                   vector<pair<long long, int> >,

                   greater<pair<long long, int> > > que;

    que.push(make_pair(dist[s], s));



    // Dijkstra 法の反復を開始

    while (!que.empty()) {

        // v: 使用済みでない頂点のうち d[v] が最小の頂点

        // d: v に対するキー値

        int v = que.top().second;

        long long d = que.top().first;

        que.pop();



        // d > dist[v] は，(d, v) がゴミであることを意味する

        if (d > dist[v]) continue; 



        // 頂点 v を始点とした辺たちを緩和

        for (auto e : G[v]) {

            if (chmin(dist[e.to], dist[v] + e.w)) {

                // 更新があるならヒープに新たに追加

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

            }

        }

    }

    

    // 結果出力

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

        if (dist[v] < INF) cout << dist[v] << endl;

        else cout << "INF" << endl;

    }

}




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

#include <cassert>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

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

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

#define vi vector<int>

#define pb push_back

#define INF 999999999

//#define INF (1LL<<59)



#define MAX_V 100000



struct edge{int to,cost;};

vector<edge> G[MAX_V];

int d[MAX_V];



void dijkstra(int s){

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

    rep(i,MAX_V)d[i]=INF;

    d[s]=0;

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

    

    while(que.size()){

        pii p=que.top();

        que.pop();

        

        int v=p.second;

        if(d[v]<p.first)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;

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

            }

        }

    }

}







int main(){

    int v,e,s;

    cin>>v>>e>>s;

    rep(i,e){

        int a,b,c;

        cin>>a>>b>>c;

        G[a].pb(edge{b,c});

    }

    

    dijkstra(s);

    

    rep(i,v){

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

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

    }

}

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

#include <cassert>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

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

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

#define vi vector<int>

#define pb push_back

#define INF 999999999

//#define INF (1LL<<59)



//verified AOJ GRL_1

#define MAX_V 100000

struct edge{int to,cost;};

vector<edge> G[MAX_V];



void dijkstra(int s, vector<int> &d){

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

    rep(i,d.size())d[i]=INF;

    d[s]=0;

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

    

    while(que.size()){

        pii p=que.top();

        que.pop();

        

        int v=p.second;

        if(d[v]<p.first)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;

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

            }

        }

    }

}





int main(){

    int v,e,s;

    cin>>v>>e>>s;

    rep(i,e){

        int a,b,c;

        cin>>a>>b>>c;

        G[a].pb(edge{b,c});

    }

    

    vi d(v);

    dijkstra(s,d);

    

    rep(i,v){

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

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

    }

}

// Fastest known solution for this problem: