#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,m,wt;
cin>>n>>m;
vector<pair<int,int>>graph[n+1];
for(int i=0;i<m;i++)
{
int a,b,wt;
cin>>a>>b>>wt;
graph[a].push_back(make_pair(b,wt));
graph[b].push_back({a,wt});
}
int source;
cin>>source;
vector<int>dist(n+1,INT_MAX);
dist[source]=0;
priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>pq;

pq.push(make_pair(0,source)); //distance,source
while(!pq.empty())
{
int distt=pq.top().first;
int prev=pq.top().second;
pq.pop();
for(auto it :graph[prev])
{
int next=it.first;
int next_dist=distt+it.second;
if(dist[next]>next_dist)
{
dist[next]=next_dist;
pq.push(make_pair(dist[next],next));
}
}
}
cout<<"The distance from "<<source<<" is:"<<endl;
for(int i=1;i<=n;i++)
{
cout<<i<<" "<<dist[i]<<endl;
}
}