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

#define pb push_back
#define mp make_pair
#define PII pair<int,int>

using namespace std;

const int NMAX = 50005;
const int INF = (1<<31)-1;

int n,m,i,j,x,y,c,Dist[NMAX],from,where,cost_where;
vector<PII> V[NMAX];

struct cmp
{
    bool operator() (PII a,PII b)
    {
        return a.second>b.second;
    }
};

priority_queue<PII,vector<PII>,cmp> Q;

void Read()
{
    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);
        V[x].pb(mp(y,c));
    }
}
void Dijkstra()
{
    for(i=2;i<=n;i++) Dist[i]=INF;
    Q.push(mp(1,0));
    while(!Q.empty())
    {
        from=Q.top().first;
        Q.pop();
        for(vector<PII>::iterator it=V[from].begin();it!=V[from].end();it++)
        {
            where=it->first;
            cost_where=it->second;
            if(Dist[from]+cost_where<Dist[where])
            {
                Dist[where]=Dist[from]+cost_where;
                Q.push(mp(where,Dist[where]));
            }
        }
    }
}
void Print()
{
    for(i=2;i<=n;i++)
        if(Dist[i]==INF) printf("0 ");
        else printf("%d ",Dist[i]);
}
int main()
{
    Read();
    Dijkstra();
    Print();
    return 0;
}