#include <iostream>
#include <vector>
#include <queue>
#include <fstream>

using namespace std;

struct Node{
	int value, distance;
};

int verticesNumber, edgeNumber, sourceNode, endNode;
vector<Node>* adj;

int bfs(int, int);
void addEdge(int, int, int);
int main(){

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

	read>>verticesNumber>>edgeNumber>>sourceNode>>endNode;
	sourceNode--;
	endNode--;
	adj = new vector<Node>[verticesNumber];

	for(int i=0; i<edgeNumber; i++){
		int x, y, d;
		read>>x>>y>>d;
		x--;
		y--;
		addEdge(x, y, d);
	}

	for(int i=0; i<verticesNumber; i++){
		vector<Node>::iterator it = adj[i].begin();
		for(; it!=adj[i].end(); ++it)
			cout<<it->distance<<" ";
		cout<<endl;
	}

	write<<bfs(sourceNode, endNode);

	return 0;
}

void addEdge(int v, int w, int distance){

	Node newConnection;
	newConnection.value = w;
	newConnection.distance = distance;

	adj[v].push_back(newConnection);

	newConnection.value = v;
	newConnection.distance = -distance;

	adj[w].push_back(newConnection);

}

int bfs(int sourceNodeInt, int endNode){

	bool *visited = new bool[verticesNumber];
	for(int i=0; i<verticesNumber; i++)
		visited[i] = false;
	queue<Node>Q;

	Node sourceNode;
	sourceNode.value = sourceNodeInt;
	sourceNode.distance = 0;
	int distance = 0;
	visited[sourceNodeInt] = true;

	Q.push(sourceNode);
	while(!Q.empty()){
		sourceNode = Q.front();

		if(sourceNode.value == endNode)
			return distance;
		Q.pop();
		vector<Node>::iterator it = adj[sourceNode.value].begin();
		for(; it!=adj[sourceNode.value].end(); ++it){
			if(!visited[it->value]){
				visited[it->value] = true;
				distance+=it->distance;
				Node newNode;
				newNode.value = it->value;
				newNode.distance = it->distance;

				Q.push(newNode);
			}
		}
	}

}