#include <fstream>
#include <vector>
#include <queue>
using namespace std;

ifstream fin("dijkstra.in");
ofstream fout("dijkstra.out");

int main()
{
    vector<unsigned short> *a;
    vector<unsigned short> *b;
    queue<unsigned short> q;
    int n,m,i,j,k,*v;
    fin>>n>>m;
    v=new int[n+1];
    a=new vector<unsigned short>[n+1];
    b=new vector<unsigned short>[n+1];
    for(v[1]=0,i=2;i<=n;++i)
        v[i]=500000000;
    while(m)
    {
        fin>>i>>j>>k;
        a[i].push_back(j);
        b[i].push_back(k);
        m--;
    }
    for(q.push(1);q.size();q.pop())
        for(i=0;i<a[q.front()].size();++i)
            if(v[q.front()]+b[q.front()][i]<v[a[q.front()][i]])
            {
                if(v[a[q.front()][i]]==500000000)
                    q.push(a[q.front()][i]);
                v[a[q.front()][i]]=v[q.front()]+b[q.front()][i];
            }
    for(i=2;i<=n;++i)
        fout<<v[i]<<" ";
}