#include <cstdio>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
int n,m,D[50005];
vector < pair<int,int> > G[50005];
bool used[50005];
#define pb push_back
#define mp make_pair
#define INF ((1<<31)-1)
void dijkstra()
{
    priority_queue < pair<int,int> > h;
    h.push(mp(0,1));
    while (!h.empty())
    {
        pair <int,int> nod=h.top();
        h.pop();
        if (used[nod.second]) continue;
        int x=nod.second;
        used[x]=true;
        for (vector< pair<int,int> >::iterator it=G[x].begin();it!=G[x].end();it++)
        {
            if (it->second+D[x]<D[it->first])
            {
                D[it->first]=it->second+D[x];
                h.push(mp(-D[it->first],it->first));
            }
        }
    }
}
int main()
{
    freopen("dijkstra.in","r",stdin);
    freopen("dijkstra.out","w",stdout);
    scanf("%d %d",&n,&m);
    int a,b,c;
    while (m--)
    {
        scanf("%d %d %d",&a,&b,&c);
        G[a].pb(mp(b,c));
    }
    for (int i=2;i<=n;i++) D[i]=INF;
    D[1]=0;
    dijkstra();
    for (int i=2;i<=n;i++)
        printf("%d ",(D[i]==INF)?0:D[i]);
    return 0;
}