#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int maxn = 1e5 + 10;
const int INF = 2e9;
vector<pair<int, int>> graph[maxn];


int main() {
    ios_base::sync_with_stdio(false);
    int n, m;
    cin >> n >> m;

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

        graph[a].push_back({b, c});
        graph[b].push_back({a, c});
    }


    int S, E;
    cin >> S >> E;


    vector<bool> visited(n, false);
    vector<int> dist(n, INF);

    dist[S] = 0;

    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    pq.push({S, 0});


    while(!pq.empty()) {
        pair<int, int> node = pq.top();
        pq.pop();

        int c_node = node.first;
        int c_shortest_path = node.second;

        if(visited[c_node]) continue;
        visited[c_node] = true;



        for(pair<int, int> neighbour: graph[c_node]) {
            if(!visited[neighbour.first] and neighbour.second + c_shortest_path < dist[neighbour.first]) {
                dist[neighbour.first] = neighbour.second + c_shortest_path;
                pq.push({neighbour.first, dist[neighbour.first]});
            }
        }


    }


    for(int i = 0; i < n; i++) {
        cout << i << " " << dist[i] << endl;
    }
     return 0;
}
/*
 5 6
 0 1 19
 0 2 14
 1 2 20
 2 3 10
 3 4 13
 2 4 100
 0 4
 **/