#include "bits/stdc++.h"
using namespace std;

#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)   FOR(i,0,n)
#define ALL(a)  (a).begin(),(a).end()
#define LL long long
#define OFFSET 200000



vector< vector<int> > pl_d(400001);
vector< vector<int> > pl_r(400001);
vector< vector<int> > pl_u(400001);
vector< vector<int> > pl_l(400001);
vector< vector<int> > df_u(400001);
vector< vector<int> > df_d(400001);
vector< vector<int> > df_r(400001);
vector< vector<int> > df_l(400001);
vector< vector<int> > xs_u(200001);
vector< vector<int> > xs_d(200001);
vector< vector<int> > ys_l(200001);
vector< vector<int> > ys_r(200001);


int minimum_col(const vector<int> &v1,const vector<int> &v2,int rat){
  if(!(v1.size() > 0 && v2.size() > 0))return 10000000;
  int j = 0;
  int ret = 10000000;
  REP(i,v1.size()){
    int x_ = v1[i];
    //cerr<<x_<<" "<<v2[j]<<endl;
    while(x_ > v2[j]){
      //cerr<<"dbg "<<x_<<" "<<v2[j]<<endl;
      j++;
      if(j == v2.size())return ret*rat;
    }
    ret = min(ret,v2[j] - x_);
  }
  return ret*rat;
}


int main(){
  int x[200000],y[200000];
  char u[200000];

  int n;
  cin>>n;
  REP(i,n){
    cin>>x[i]>>y[i]>>u[i];
    switch(u[i]){
      case 'U':
        pl_u[x[i]+y[i]].push_back(x[i]);
        df_u[x[i]-y[i]+OFFSET].push_back(x[i]);
        xs_u[x[i]].push_back(y[i]);
        break;
      case 'D':
        pl_d[x[i]+y[i]].push_back(x[i]);
        df_d[x[i]-y[i]+OFFSET].push_back(x[i]);
        xs_d[x[i]].push_back(y[i]);
        break;
      case 'L':
        pl_l[x[i]+y[i]].push_back(x[i]);
        df_l[x[i]-y[i]+OFFSET].push_back(x[i]);
        ys_l[y[i]].push_back(x[i]);
        break;
      case 'R':
        pl_r[x[i]+y[i]].push_back(x[i]);
        df_r[x[i]-y[i]+OFFSET].push_back(x[i]);
        ys_r[y[i]].push_back(x[i]);
        break;
    }
  }
  int ret = 10000000;

  for(auto &e : pl_u){
    sort(ALL(e));
  }
  for(auto &e : pl_d){
    sort(ALL(e));
  }
  for(auto &e : df_u){
    sort(ALL(e));
  }
  for(auto &e : df_d){
    sort(ALL(e));
  }
  for(auto &e : pl_l){
    sort(ALL(e));
  }
  for(auto &e : pl_r){
    sort(ALL(e));
  }
  for(auto &e : df_r){
    sort(ALL(e));
  }
  for(auto &e : df_l){
    sort(ALL(e));
  }
  for(auto &e : xs_u){
    sort(ALL(e));
  }
  for(auto &e : xs_d){
    sort(ALL(e));
  }
  for(auto &e : ys_l){
    sort(ALL(e));
  }
  for(auto &e : ys_r){
    sort(ALL(e));
  }

  REP(i,400001)ret = min(ret,minimum_col(pl_d[i],pl_l[i],10));
  REP(i,400001)ret = min(ret,minimum_col(df_u[i],df_l[i],10));
  REP(i,400001)ret = min(ret,minimum_col(pl_r[i],pl_u[i],10));
  REP(i,400001)ret = min(ret,minimum_col(df_r[i],df_d[i],10));
  REP(i,200001)ret = min(ret,minimum_col(xs_u[i],xs_d[i],5));
  REP(i,200001)ret = min(ret,minimum_col(ys_r[i],ys_l[i],5));
  
  if(ret >= 10000000)cout<<"SAFE"<<endl;
  else cout<<ret<<endl;
  return 0;
}

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500010;
const int INF = 1000000010;

int n, m;
int cntNode;

int dist[MAXN];

vector<int> adj[MAXN];
vector<int> weight[MAXN];

deque<int> d;

map<int,int> indNode[MAXN];

void BFS01(int s)
{
	for(int i = 1 ; i <= cntNode ; i++)
		dist[i] = INF;

	dist[s] = 0;
	d.push_front( s );

	while( !d.empty() )
	{
		int cur = d.front();
		d.pop_front();

		for(int i = 0 ; i < (int)adj[cur].size() ; i++)
		{
			int viz = adj[cur][i];
			int w = weight[cur][i];

			if( dist[viz] <= dist[cur] + w ) continue;

			dist[viz] = dist[cur] + w;

			if( w == 0 ) d.push_front( viz );
			else d.push_back( viz );
		}
	}
}

int getExpandedNode(int node, int color)
{
	if( indNode[node][color] == 0 )
		indNode[node][color] = ++cntNode;

	return indNode[node][color];
}

void addEdge(int U, int V, int W)
{
	adj[U].push_back( V );
	weight[U].push_back( W );
}

int main()
{
	scanf("%d %d",&n,&m);

	cntNode = n;

	for(int i = 1 ; i <= m ; i++)
	{
		int U, V, C;
		scanf("%d %d %d",&U,&V,&C);

		int A = getExpandedNode( U , C );
		int B = getExpandedNode( V , C );

		addEdge( A , B , 0 );
		addEdge( B , A , 0 );
	}

	for(int i = 1 ; i <= n ; i++)
	{
		for(auto it = indNode[i].begin() ; it != indNode[i].end() ; it++)
		{
			addEdge( i , it->second , 0 );
			addEdge( it->second , i , 1 );
		}
	}

	BFS01( 1 );

	if( dist[n] == INF ) printf("-1\n");
	else printf("%d\n",dist[n]);
}