#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#define pb push_back
#define inf 99999999
using namespace std;
vector < pair<int,int> > v[5005];
vector <pair<int,int> >::iterator it;
priority_queue < pair<int,int> > q;
int n,m,a,b,c,d[55001];
bool ok[55001];
inline void Copac()
{
    q.push(make_pair(0,1));
    int x;
    while(!q.empty())
    {
        x = q.top().second;
        q.pop();
        for(it=v[x].begin(); it!=v[x].end();it++)
        {
            if( d[(*it).second] > d[x]+(*it).first )
            {
                d[(*it).second] = d[x]+(*it).first;
                q.push(make_pair(-d[(*it).second],(*it).second));
            }
        }
    }
}
int main()
{
    int i;
    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",&a,&b,&c);
        v[a].pb(make_pair(c,b));
    }
    for(i=2; i<=n; i++)
        d[i]=inf;
    d[1]=0;
    Copac();
    for(i=2; i<=n; i++)
        printf("%d ",d[i]==inf ? 0 : d[i]);
    return 0;
}