#include <bits/stdc++.h>

using namespace std;

ifstream in ("sate.in");
ofstream out ("sate.out");

#define MAX_N 30000

struct muchie
{
    int dir;
    int km;
};

int finish;

int dist[MAX_N];

vector<muchie>graf[MAX_N];

bool f[MAX_N];

queue<int> Q;

void BFS()
{
    int node;
    while(Q.size() != 0)
    {
        node = Q.front();
        Q.pop();
        f[node] = 1;
        for(int x = 0; x < graf[node].size(); ++x)
        {
            if(f[graf[node][x].dir] == 0)
            {
                //cout << graf[node][x] << " ";
                Q.push(graf[node][x].dir);
                f[graf[node][x].dir] = 1;
                dist[graf[node][x].dir] = dist[node] + graf[node][x].km;
                if(graf[node][x].dir == finish)
                    return;
            }
        }
    }
}

int main()
{
    int n, m, x, y, k, p, a, start;
    in >> n >> m >> start >> finish;
    for(int i = 0; i < m; ++i)
    {
        in >> x >> y >> a;
        graf[x].push_back({y, a});
        graf[y].push_back({x, a});
    }
    Q.push(start);
    BFS();

    for(int i = 0; i <= n; ++i)
    {
        cout << i << " " << dist[i] << '\n';
    }

    out << dist[finish];
    return 0;
}