#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
#define pi 3.141592653589793238
#define int long long
#define ll long long
#define ld double
using namespace __gnu_pbds;
using namespace std;
template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
mt19937 rnd(time(0));


long long powm(long long a, long long b,long long mod) {
    long long res = 1;
    while (b > 0) {
        if (b & 1)
            res = res * a %mod;
        a = a * a %mod;
        b >>= 1;
    }
    return res;
}

ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b); 
     
}

vector<vector<pair<int,int> > >adj[26];
int dis[1005][1005];
void dik(int so,int des)
{
    dis[so][des]=0;
    priority_queue<pair<int,pair<int,int> >,vector<pair<int,pair<int,int> > >,greater<pair<int,pair<int,int> > > >qq;

    qq.push({0,{so,des}});

    while(!qq.empty())
    {
        auto pp=qq.top();
        qq.pop();
        if(dis[pp.second.first][pp.second.second]<pp.first)
            continue;

        for(int i=0;i<26;i++)
        {
            for(auto j:adj[i][pp.second.first])
            {
                for(auto k:adj[i][pp.second.second])
                {
                    if(dis[j.first][k.first]>pp.first+j.second+k.second)
                    {
                        dis[j.first][k.first]=pp.first+j.second+k.second;
                        qq.push({dis[j.first][k.first],{j.first,k.first}});
                    }
                }
            }
        }
    }
}



signed main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(0);

    int t = 1;
    // cin>>t;
    while(t--)
    {
        int n,m,so,des;
        cin>>n>>m; so = 1; des = n;
        for(int i=0;i<26;i++)
        {
            adj[i].clear();
            adj[i].resize(n+1);
        }

        for(int i=1;i<=n;i++)
            for(int j=1;j<=n;j++)
                dis[i][j]=1e17;
        char w;
        int x,y,z;
        vector<pair<int,pair<int,int> > >edge;
        for(int i=0;i<m;i++)
        {
            cin>>x>>y>>w;
          z=1;
            edge.push_back({z,{x,y}});
            adj[w-'a'][x].push_back({y,z});
            adj[w-'a'][y].push_back({x,z});            
        }
        dik(so,des);

        int mn=1e17;
        for(auto i:edge)
        {
            mn=min(mn,i.first+dis[i.second.first][i.second.second]);
            mn=min(mn,i.first+dis[i.second.second][i.second.first]);
        }

        for(int i=1;i<=n;i++)
            mn=min(mn,dis[i][i]);
        if(mn==1e17)
            cout<<-1<<'\n';
        else
            cout<<mn<<'\n';

    }


}
#include <bits/stdc++.h>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define rrep(i,b,a) for(int i=b;i>=a;i--)
#define fori(a) for(auto i : a )
#define all(a) begin(a), end(a)
#define set(a,b) memset(a,b,sizeof(a))
#define sz(a) a.size()
double pi=acos(-1);
#define ll long long
#define ull unsigned long long
#define pb push_back
#define PF push_front //deque
// #define mp make_pair
#define pq priority_queue
const ll mod=1000000007;
#define f first
#define s second
#define pii pair< ll, ll >
#define vi vector<int>
#define vpii vector<pii>
#define debug(v) for(auto i:v) cout<<i<<" ";
#define tc int t; cin >> t; while(t--)
using namespace std;
void optimizeIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}
const int MAX=200005;
vector<int> adj[MAX];
int n,l;
void add_edge(int u, int v){
    adj[u].push_back(v);
    adj[v].push_back(u);
}
int timer;
vector<int> tin, tout;
vector<vector<int>> up;
ll dp[MAX],ans[MAX];
void dfs(int v, int p){
    tin[v] = ++timer;
    up[v][0] = p;
    for (int i = 1; i <= l; ++i) up[v][i] = up[up[v][i-1]][i-1];
    for (int u : adj[v])  if (u != p)   dfs(u, v);
    tout[v] = ++timer;
}

bool is_ancestor(int u, int v){ return tin[u] <= tin[v] && tout[u] >= tout[v]; }
pair<int,int> lca(int u, int v){
    if (is_ancestor(u, v)) return {1,u};
    if (is_ancestor(v, u)) return {2,v};
    for (int i = l; i >= 0; --i)  if (!is_ancestor(up[u][i], v)) u = up[u][i];
    return {3,up[u][0]};
}
void preprocess(int root) {
    tin.resize(n+1);
    tout.resize(n+1);
    timer = 0;
    l = ceil(log2(n));
    up.assign(n+1, vector<int>(l + 1));
    dfs(root, root);
}
void dfs2(int v,int p,ll rem){
  rem+= dp[v];
  ans[v]=rem;
  for(auto i:adj[v])  if(i!=p) dfs2(i,v,rem);
}
void solve(){

  cin>>n;
  pii x[n];
  rep(i,1,n){
    cin>>x[i].f>>x[i].s;
    add_edge(x[i].f,x[i].s);
  }
  preprocess(1);
  int q;
  cin>>q;
  while(q--){
    int tq,eq,xq;
    cin>>tq>>eq>>xq;
    int from,notto;
    if(tq==1){
      from=x[eq].f;
      notto=x[eq].s;
    }
    else{
      from=x[eq].s;
      notto=x[eq].f;
    }

    pii z=lca(from,notto);
    if(z.f==3){
      dp[1]+= xq;
      dp[notto]-=xq;
    }
    else if(z.f==1){
      dp[1]+=xq;
      dp[notto]-=xq;
    }
    else{
      int anc=notto,u=from;
      while(1){
        int flag=0;
        for(int i=l;i>=0;i--){
          if(up[u][i]!=anc && is_ancestor(up[u][i],anc)==anc){
            flag=1;
            u=up[u][i];
            break;
          }
        }
        if(flag==0) break;
      }
      dp[u]+=xq;
    }
  }
  dfs2(1,-1,0);
  rep(i,1,n+1) cout<<ans[i]<<'\n';
}

int main(){
    optimizeIO();
    solve();
}
