#include <fstream>
#include <vector>
#include <queue>
#define inf 2000000000

using namespace std;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,p,i,x,y,c,vfmin,lungime,dmin[50005];
bool viz[50005];
struct muchie
{
    int y,cost;
};
vector <muchie> v[250005];
struct cmp
{
    bool operator() (const int &x, const int &y)
    {
        return dmin[x]>dmin[y];
    }
};

priority_queue <int, vector <int>, cmp> H;

int main()
{
    fin>>n>>m;
    for (i=1; i<=m; i++)
    {
        fin>>x>>y>>c;
        muchie elem;
        elem.y=y;
        elem.cost=c;
        v[x].push_back(elem);
    }
    for (i=2; i<=n; i++)
        dmin[i]=inf;
    H.push(1);
    while (!H.empty())
    {
        vfmin=H.top();
        H.pop();
        if (viz[vfmin]==0)
        {
            viz[vfmin]=1;
            lungime=v[vfmin].size();
            for (i=0; i<lungime; i++)
                if (dmin[v[vfmin][i].y]>dmin[vfmin]+v[vfmin][i].cost)
            {
                dmin[v[vfmin][i].y]=dmin[vfmin]+v[vfmin][i].cost;
                viz[v[vfmin][i].y]=0;
                H.push(v[vfmin][i].y);
            }
        }
    }
    for (i=2; i<=n; i++)
        if (dmin[i]==inf) fout<<"0 ";
            else fout<<dmin[i]<<" ";
    return 0;
}