#include <fstream>
#define maxim 50001
#include <list>

using namespace std;

struct muchie
{
    int l; short int vf;
};

muchie x;

list <muchie> nod[maxim];

int dist[maxim], minn, viz[maxim], n, m, a, b, lung, vfm;

int stab_drum(int varf)
    {
        int v=vfm;
        minn=1000000;
        for (list<muchie>::iterator j=nod[varf].begin(); j!=nod[varf].end(); ++j)
            {
                x=*j;
                if(dist[x.vf]>(dist[varf]+x.l)||dist[x.vf]==0)
                    {
                        dist[x.vf]=dist[varf]+x.l;
                    }
            }
        for (int i = 1; i<=n; ++i)
            if(dist[i]<minn&&viz[i]==0&&dist[i]!=0)
                {
                    minn=dist[i];
                    v=i;
                }
        return v;
    }

int main()
{
    ifstream in ("dijkstra.in");
    ofstream out ("dijkstra.out");
    in>>n>>m;
    while(m--)
        {
            in>>a>>b>>lung;
            x.vf=b;
            x.l=lung;
            nod[a].push_back(x);
        }
    vfm=1;
    for(int i=1; i<=n; ++i)
        {
            viz[vfm]=1;
            vfm=stab_drum(vfm);
        }
    for(int i=2; i<=n; ++i)
        out<<dist[i]<<" ";
    in.close();
    out.close();
    return 0;
}