dijkstra

#include <bits/stdc++.h>
using namespace std;
#define MX 105
#define INF 100000000
struct node{
    int val;
    int cost;
};
class cmp
{public:
bool operator()(node &A,node &B){
if(A.cost>B.cost)return true;
return false;}
};
vector<node>G[MX];
bool vis[MX];
int dist[MX];
void reset()
{
    for(int i=0;i<MX;i++)
    {   G[i].clear();
    vis[i]=0;
    dist[i]=INF;
    }
}
void dijkstra(int source)
{ priority_queue<node,vector<node>,cmp>pq;
pq.push({source,0});
while(!pq.empty()){
    node current=pq.top();
    pq.pop();
    int val=current.val;
    int cost=current.cost;
    if(vis[val]==1)continue;
    dist[val]=cost;
    vis[val]=1;
    for(int i=0;i<G[val].size();i++)
    {
    int nxt=G[val][i].val;
    int nxtcost=G[val][i].cost;
    if(vis[nxt]==0)
    {pq.push({nxt,cost+nxtcost});
}
}
}}

int main() {
 int nodes,edges;
 cin>>nodes>>edges;
for(int i=1;i<=edges;i++)
{int u,v,w;
cin>>u>>v>>w;
G[u].push_back({v,w});}
int source;
cin>>source;
dijkstra(source);
for(int i=1;i<=nodes;i++)
{cout<<i<<" ";
if(dist[i]==INF) cout<<"INF"<<endl;
  else cout<<dist[i]<<endl;
}
return 0;
}