#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
const ll INF=0x3f3f3f3f3f3f3f;
const double pi=3.1415926535897932384626;
inline ll read(){
	ll x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x=(x<<1)+(x<<3)+(ch^48);
		ch=getchar();
	}
	return x*f;
}
const int maxn=2e3+5;
int n,m,u,v,w,dis[maxn][maxn],a[maxn];
struct node{
	int x,y;
	bool operator<(const node &a)const{
		return y>a.y;
	}
};
vector<node> g[maxn];
void dijkstra(int u){
	dis[u][u]=0;
	queue<node> q;
	q.push({u,0});
	while(!q.empty()){
		node now=q.front();
		q.pop();
		int from=now.x;
		for(auto it:g[from]){
			int to=it.x,w=it.y;
			if(dis[u][from]+w<dis[u][to]){
				dis[u][to]=dis[u][from]+w;
				q.push({to,dis[u][to]});
			}
		}
	}
} 
int main(){
	n=read(),m=read();
	memset(a,inf,sizeof(a));
	memset(dis,inf,sizeof(dis));
	for(int i=1;i<=m;++i){
		u=read(),v=read(),w=read();
		if(u==v) a[u]=min(a[u],w);
		else g[u].push_back({v,w});
	}
	for(int i=1;i<=n;++i) dijkstra(i);
	for(int i=1;i<=n;++i){
		int ans=inf;
		for(int j=1;j<=n;++j){
			if(i==j) continue;
			ans=min(ans,dis[i][j]+dis[j][i]);
		}
		ans=min(ans,a[i]);
		if(ans==inf) printf("-1\n");
		else printf("%d\n",ans);
 	}
	return 0;
}
#include <bits/stdc++.h>
using namespace std;

int main() {
    int n, m;
    cin>> n >> m;
    vector<pair<int, int>> a(m);
    for (auto& [A, B] : a) cin>> A >> B;
    int k; cin>> k;
    vector<pair<int, int>> b(k);
    for (auto& [C, D] : b) cin>> C >> D;
    
    int ans = 0;
    for (int bit=0; bit<(1<<k); bit++) {
        vector<bool> ball(n);
        for (int i=0; i<k; i++) {
            const auto [C, D] = b[i];
            ball[bit & 1<<i ? C : D] = 1;
        }
        int cnt = 0;
        for (auto [A, B] : a) if (ball[A] && ball[B]) cnt++;
        if (ans < cnt) ans = cnt;
    }
    
    cout << ans << endl;
    return 0;
}