stablegradients/pie-gem5-pairs huggingface dataset:
// Slower C++ solution:
#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;

}




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

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

}

	

	


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

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

}

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

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

}

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

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

}

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

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

}

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

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

}

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

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

}

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

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

}

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

}