#include<cstdio>
#include<vector>
#include<queue>
#include<set>
using namespace std;
const int inf=2000000000;
struct sp
{
    int y,co;
};
int co[50005];
struct innt
{
    int y;
    const bool operator <(const innt & other) const
    {
        if(co[y]!=co[other.y])
            return co[y]>co[other.y];
        return y<other.y;
    };
};
vector<sp> ve[50005];
priority_queue<innt> pq;
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    int n,m,i,x,lm;
    sp tm;
    innt tn,tp;
    scanf("%d%d",&n,&m);
    for(i=1; i<=m; i++)
    {
        scanf("%d%d%d",&x,&tm.y,&tm.co);
        ve[x].push_back(tm);
    }
    for(i=2; i<=n; i++)
        co[i]=inf;
    co[1]=0;
    tn.y=1;
    pq.push(tn);
    while(!pq.empty())
    {
        tn=pq.top();
        pq.pop();
        for(i=ve[tn.y].size()-1; i>=0; i--)
            if(co[tn.y]+ve[tn.y][i].co<co[ve[tn.y][i].y])
            {
                co[ve[tn.y][i].y]=co[tn.y]+ve[tn.y][i].co;
                tp.y=ve[tn.y][i].y;
                pq.push(tp);
            }
    }
    for(i=2; i<=n; i++)
        if(co[i]<inf)
            printf("%d ",co[i]);
        else
            printf("0 ");
    printf("\n");
    return 0;
}