bfs any wait

// In the name of Allah.
// We're nothing and you're everything.
// Ya Ali!
/*
                  ,     \    /      ,
                 / \    )\__/(     / \
                /   \  (_\  /_)   /   \
           ____/_____\__\@  @/___/_____\____
          |             |\../|              |
          |              \VV/               |
          |        ------___-------         |
          |__________Chuta Dragon___________|
           |    /\ /      \\       \ /\    |
           |  /   V        ))       V   \  |
           |/     `       //        '     \|
           `              V                '
*/

#include<bits/stdc++.h>
using namespace std;
typedef long long  ll;
typedef pair<ll,ll> pll;
#define fastread() (ios_base:: sync_with_stdio(false),cin.tie(NULL))
#define fi first
#define se second
#define pb push_back
ll const MOD=1000000007;
const int M= 2e5 + 10;
///-------------------------------------------------------------------------------------------------///
///                KARMA IS LIKE 69,,, YOU GET WHAT YOU GIVE                                        ///
///-------------------------------------------------------------------------------------------------///
#define eb emplace_back

vector<pll>v[M+10];
ll n,m;
bool vis[M+10];
ll cost[M+1];
void BFS(ll s)
{
    vis[s]=true;

    cost[s]=0;

    queue<ll>q;

    q.push(s);


    while(!q.empty())
    {
        ll u=q.front();
        q.pop();

       for(auto x:v[u])
       {
           ll node=x.fi;
           ll w=x.se;

           if(!vis[node])
           {
               cout<<node<<" "<<u<<endl;

               cost[node]=cost[u]+w;

               vis[node]=true;
               q.push(node);

           }


       }

    }












}





void input()
{

     cin>>n>>m;

    ll a,b,c;
    for(ll i=0;i<m;i++)
    {
        cin>>a>>b>>c;

       v[a].eb(b,c);

       v[b].eb(a,c);

    }
}


int main()
{
    fastread();

    input();


    ll s;


   cin>>s;



    BFS(s);


 cout<<endl<<endl;

    for(ll i=1;i<=n;i++)
    {
        cout<<i<<" "<<cost[i]<<endl;
    }




}
/*

6 6
1 2 5
1 3 4
2 4 5
2 6 5
3 5 4
3 4 4

3

*/