#include <cstdio>
#include <vector>
#include <queue>

using namespace std;
const int inf=2000000000;
struct element
{
    int y,cost;
} e1;
int n,m,i,x,y,c,vfmin,lungime,dmin[50005];
bool viz[50005];

vector <element> v[50005];

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

struct cmp
{
    bool operator() (const int &x, const int &y)
    {
        return dmin[x]>dmin[y];
    }
};

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

int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d%d",&n,&m);
    for (i=1; i<=m; i++)
    {
        scanf("%d%d%d",&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();
        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 && viz[v[vfmin][i].y]==0)
            {
                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) printf("0 ");
            else printf("%d ",dmin[i]);
    printf("\n");
    return 0;
}