#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #define inf 99999999using namespace std;const int maxn=110;int e,dis[maxn],vis[maxn],to[maxn],be[maxn],ne[maxn],w[maxn];void add(int x,int y,int z){	to[++e]=y;	ne[e]=be[x];	be[x]=e;	w[e]=z;}queue
         
          q;int main(){ int i,j,k,m,n; scanf("%d%d",&n,&m); for(i=1;i<=m;i++){ int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add(y,x,z); } for(i=1;i<=n;i++)dis[i]=inf; dis[1]=0; vis[1]=1; q.push(1); while(!q.empty()){ int u=q.front(); q.pop(); vis[u]=0; for(i=be[u];i;i=ne[i]){ int v=to[i]; if(dis[v]>dis[u]+w[i]){ dis[v]=dis[u]+w[i]; if(!vis[v]){ q.push(v); vis[v]=1; } } } } for(i=1;i<=n;i++){ printf("%d",dis[i]); } return 0;}/*5 71 2 21 5 102 3 32 5 73 4 44 5 55 3 6*/