#include <fstream>
#include <vector>
#include <queue>
using namespace std;
ifstream cin("dijkstra.in");
ofstream cout("dijkstra.out");
const int NMAX=50000,INF=1000000000;
int n,m;
vector<int>v[NMAX+5];
vector<int>d[NMAX+5];
int l[NMAX+5],best[NMAX+5];
bool pedrum[NMAX+5];
int a,b,c;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>a>>b>>c;
        v[a].push_back(b);
        d[a].push_back(c);
        l[a]++;
    }
    for(int i=2;i<=n;i++)
        best[i]=INF;
    queue<int>q;
    pedrum[1]=1;
    q.push(1);
    while(!q.empty())
    {
        int nod=q.front();
        q.pop();
        for(int i=0;i<l[nod];i++)
        {
            int nou=v[nod][i],cost=d[nod][i];
            if(best[nod]+cost<best[nou])
            {
                if(pedrum[nou]==0)
                {
                    pedrum[nou]=1;
                    q.push(nou);
                }
                best[nou]=best[nod]+cost;
            }
        }
        pedrum[nod]=0;
    }
    for(int i=2;i<=n;i++)
    {
        if(best[i]==INF)
            cout<<0<<" ";
        else
            cout<<best[i]<<" ";
    }
    return 0;
}
/**
**/