#include <fstream>
#include <vector>
#include <queue>

using namespace std;
const int inf=2000000000;
ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");
int n,m,i,x,y,c,vfmin,dmin[50005];
struct element
{
    int y,cost;
} e1;

element make_elem(int y, int c)
{
    element elem;
    elem.y=y;
    elem.cost=c;
    return elem;
}

vector <element> v[50005];

class comparvf
{
public:
    bool operator() (const int &x, const int &y)
    {
        return dmin[x]>dmin[y];
    }
};

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

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