#include <cstdio>
#include <vector>
#include <utility>
#include <queue>
#define pb push_back
#define inf 99999999
using namespace std;
vector < pair<int,int> > v[50005];
vector <pair<int,int> >::iterator it;
priority_queue < pair<int,int> > q;
int n,m,a,b,c,d[50005];
bool ok[50005];
inline void Copac()
{
    q.push(make_pair(0,1));
    int x;
    while(!q.empty())
    {
        x = q.top().second;
        if(!ok[x])
        {
            ok[x] = true;
            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;
}