#include <fstream>
#include <vector>
#include <queue>
#include <bitset>
#define nmax 50002
#define inf 20000000
using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");


struct nod{
    int v,c;
};

class cmp{
public:
    bool operator()(nod A,nod B)
    {
        return A.c>B.c;
    }
};

vector <nod> graf[nmax];
priority_queue <nod,vector<nod>,cmp> coada;
int dist[nmax];

bitset <nmax> viz;

int main()
{
    int n,m,x,y,c,ma,ns;
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        fin>>x>>y>>c;
        graf[x].push_back({y,c});
        graf[y].push_back({x,c});
    }
    for(int i=1;i<=n;i++)
        dist[i]=inf;
    coada.push({1,0});
    dist[1]=0;
    ma=0;
    while(ma!=inf)
    {
        ma=inf;
        for(int i=1;i<=n;i++)
        {
            if(dist[i]<ma&&viz[i]!=0)
            {
                ma=dist[i];
                ns=i;
            }
        }
        if(ma!=inf)
        {
            int lg=graf[ns].size()-1;
            for(int i=0;i<lg;i++)
            {
                int v=graf[ns][i].v;
                int cost=graf[ns][i].c;
                if(ma+cost<dist[v])
                {
                    dist[v]=ma+cost;
                    coada.push({dist[v],v});
                }
            }
        }
        viz[ns]=1;
    }
    for(int i=1;i<=n;i++)
        if(dist[i]==inf)
            dist[i]=0;
    for(int i=2;i<=n;i++)
        fout<<dist[i];
    return 0;
}