#include<fstream>
#include<vector>
#define inf 2147483648
using namespace std;
ifstream f("dijkstra.in");
ofstream g("dijkstra.out");
int n, m, nod, i, vecin, cost;
long long d[50003], minim;
bool viz[50003];
vector <pair <int, int> > l[250003];
int main()
{
    f>>n>>m;
    for(i=1;i<=m;i++)
    {
        int x, y, c;
        f>>x>>y>>c;
        l[x].push_back(make_pair(y, c));
    }
    for(i=2;i<=n;i++)
        d[i]=inf;
    for(;;)
    {
        minim=inf;
        for(i=1;i<=n;i++)
            if(d[i]<minim && viz[i]==0)
            {
                minim=d[i];
                nod=i;
            }
        viz[nod]=1;
        for(vector< pair<int, int> > :: iterator it=l[nod].begin(); it!=l[nod].end(); it++)
        {
            vecin=it->first;
            cost=it->second;
            if(d[vecin]>d[nod]+cost && viz[vecin]==0)
                d[vecin]=d[nod]+cost;
        }
        if(minim==inf)
            break;
    }
    for(i=2;i<=n;i++)
        g<<d[i]<<" ";
    return 0;
}